91. Decode Ways

mediumAsked at LinkedIn

Count the number of ways to decode a digit string where each letter maps to 1–26 — LinkedIn asks this DP problem to test whether you can enumerate valid interpretation paths under constraints, the same combinatorial reasoning used in their NLP pipeline for ambiguous entity recognition in profile text.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

A message containing letters A–Z is encoded by mapping A→1, B→2, ..., Z→26. Given a string s of digits, return the number of ways to decode it. If there is no valid decoding, return 0. A leading zero is invalid (e.g., '06' cannot be decoded as 'F').

Constraints

1 <= s.length <= 100
s contains only digits
s may contain leading zeros

Examples

Example 1

Input

s = "12"

Output

Explanation: "12" can be decoded as "AB" (1+2) or "L" (12).

Example 2

Input

s = "226"

Output

Explanation: "BZ" (2+26), "VF" (22+6), or "BBF" (2+2+6).

Example 3

Input

s = "06"

Output

Approaches

1. Recursive with memoization (top-down DP)

Define decode(i) = number of ways to decode s[i..]. At each position, try a single digit (valid if s[i]!='0') and a two-digit number (valid if 10-26). Memoize results.

Time: O(n)
Space: O(n)

function numDecodingsMemo(s) {
  const memo = new Map();
  function dp(i) {
    if (i === s.length) return 1;
    if (s[i] === '0') return 0;
    if (memo.has(i)) return memo.get(i);
    let ways = dp(i + 1); // single digit
    if (i + 1 < s.length) {
      const two = parseInt(s.slice(i, i+2));
      if (two <= 26) ways += dp(i + 2);
    }
    memo.set(i, ways);
    return ways;
  }
  return dp(0);
}

Tradeoff:

2. Bottom-up DP with two variables — optimal

dp[i] = ways to decode s[0..i-1]. dp[i] += dp[i-1] if s[i-1]!='0'; dp[i] += dp[i-2] if s[i-2..i-1] in 10..26. Use two rolling variables to cut space to O(1).

Time: O(n)
Space: O(1)

function numDecodings(s) {
  const n = s.length;
  let prev2 = 1, prev1 = s[0] === '0' ? 0 : 1;
  for (let i = 2; i <= n; i++) {
    let curr = 0;
    const oneDigit = parseInt(s[i-1]);
    const twoDigit = parseInt(s.slice(i-2, i));
    if (oneDigit !== 0) curr += prev1;
    if (twoDigit >= 10 && twoDigit <= 26) curr += prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff:

LinkedIn-specific tips

LinkedIn uses Decode Ways to test DP pattern recognition, not just memorization. The key to narrating this well: 'At each index I make two choices — take one digit (if non-zero) or two digits (if 10–26). The total ways is the sum of the ways from both choices.' Watch for the '0' trap: '30' is valid as one two-digit number but '03' is not, and a standalone '0' always kills the count. Mention the space optimization (two variables instead of an array) before the interviewer asks — it signals production-quality thinking.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Decode Ways and other LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →