Decode Ways

Difficulty: Medium

A message made only of capital letters A through Z was encoded by mapping each letter to a number: A -> "1", B -> "2", ..., Z -> "26". You're given the resulting digit string s. Because there's no separator between the encoded numbers, a run of digits can sometimes be split back into letters in more than one way (for example "11" could be "AA" or "K"). Count how many different ways s could have been decoded back into letters. A string with a "0" in a position that can't be part of a valid two-digit code (like a leading "0", or "0" on its own) contributes no valid decodings.

Examples

Input: s = "12"
Output: 2

"AB" (1, 2) or "L" (12).

Input: s = "226"
Output: 3

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

Input: s = "06"
Output: 0

A leading "0" can't stand alone as a letter and "06" isn't a valid two-digit code, so there's no valid decoding at all.

Constraints

1 <= s.length <= 100
s consists of digits only, and may contain leading zeros

Approach

Walk through the string one position at a time and ask: how many ways are there to decode everything up through here? The last "chunk" of any valid decoding is either a single digit or a pair of digits, so the count at position i is built from smaller counts you've already computed: if the single digit right before position i is a valid letter code (1 through 9), add in the count from one position earlier; if the pair of digits right before position i forms a valid letter code (10 through 26), add in the count from two positions earlier.

This is the same "build up from smaller answers" shape as Climbing Stairs, just with extra validity checks on which contributions are allowed at each step, because of the zero-digit edge cases.

Solutions

Brute Force — Plain Recursion

From each position, try consuming one digit and try consuming two digits (when valid), and recurse on what's left. Correct, but re-explores the same positions repeatedly.

function numDecodings(s) {
  const n = s.length;

  function ways(i) {
    if (i === n) return 1; // successfully consumed the whole string
    if (s[i] === "0") return 0; // no valid code starts with 0

    let total = ways(i + 1); // consume one digit

    if (i + 1 < n) {
      const twoDigit = Number(s.slice(i, i + 2));
      if (twoDigit >= 10 && twoDigit <= 26) {
        total += ways(i + 2); // consume two digits
      }
    }

    return total;
  }

  return ways(0);
}

Time: O(2^n) · Space: O(n) — recursion depth

Optimal — Bottom-Up Tabulation

Build the count of decodings for each prefix from the smallest prefix upward, reusing the two previously computed counts instead of recursing.

function numDecodings(s) {
  const n = s.length;
  if (s[0] === "0") return 0;

  // dp[i] = number of ways to decode the first i characters of s
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1; // empty prefix: exactly one way (decode nothing)
  dp[1] = 1; // first character is guaranteed non-zero by the check above

  for (let i = 2; i <= n; i++) {
    const oneDigit = Number(s[i - 1]);
    if (oneDigit >= 1) {
      dp[i] += dp[i - 1];
    }

    const twoDigit = Number(s.slice(i - 2, i));
    if (twoDigit >= 10 && twoDigit <= 26) {
      dp[i] += dp[i - 2];
    }
  }

  return dp[n];
}

Time: O(n) · Space: O(n) for the dp array (can be reduced to O(1) with two variables)