Decode Ways

A message made of capital letters was encoded by replacing each letter with its position in the alphabet: A → "1", B → "2", …, Z → "26", and then writing the numbers next to each other with no separators.

Given the resulting digit string s, count how many different letter messages could have produced it. Every digit must belong to exactly one letter code, and a code is only valid if it is a number from 1 to 26 written without a leading zero (so "05" is not a code, and neither is "0"). If s cannot be decoded at all, return 0.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Dynamic Programming · problem 157 of 169

Start simple

Recursively try taking one or two digits at each position: correct, but O(2ⁿ) time without memoisation.

The key idea

Every decoding of a prefix ends with a letter that uses either the last one digit or the last two digits. Those two cases never overlap, so the number of decodings of a prefix is the sum of the counts for each case.

Let ways[i] be the number of decodings of the first i characters, with ways[0] = 1 (the empty prefix has one decoding: nothing). Then:

• if s[i-1] is 1–9, it can be a letter on its own, contributing ways[i-1];
• if s[i-2..i-1] is between 10 and 26, it can be one letter, contributing ways[i-2].

Zeros are what make this problem interesting: a 0 can never stand alone, so it only survives as the second digit of 10 or 20. When neither case applies, ways[i] becomes 0 and stays 0 from then on, because every later count is built from earlier ones.

Each step reads only the two previous values, so two variables replace the whole table, giving linear time and constant space.

Complexity

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

Python

class Solution:
    def numDecodings(self, s):
        # prev2 = ways to decode s[:i-1], prev1 = ways to decode s[:i]
        prev2, prev1 = 1, 1 if s[0] != "0" else 0
        for i in range(1, len(s)):
            current = 0
            if s[i] != "0":                       # last letter uses one digit
                current += prev1
            if 10 <= int(s[i - 1:i + 1]) <= 26:   # last letter uses two digits
                current += prev2
            prev2, prev1 = prev1, current
        return prev1

JavaScript

var numDecodings = function(s) {
  // prev2 = ways to decode s[0..i-2], prev1 = ways to decode s[0..i-1]
  let prev2 = 1;
  let prev1 = s[0] !== "0" ? 1 : 0;
  for (let i = 1; i < s.length; i++) {
    let current = 0;
    if (s[i] !== "0") current += prev1;              // last letter uses one digit
    const pair = Number(s.slice(i - 1, i + 1));
    if (pair >= 10 && pair <= 26) current += prev2;  // last letter uses two digits
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
};

What the interviewer is checking

It checks that you can set up a clean one-dimensional DP recurrence and get the zero-handling edge cases right without a pile of special cases.

Mistakes to avoid

• Treating "0" as a valid single-digit code, or accepting two-digit codes with a leading zero such as "06".
• Accepting 27–99 as two-digit codes; only 10–26 are valid.
• Forgetting that a string starting with "0" has zero decodings.
• Using plain recursion without memoisation, which is exponential on strings like "1111…".

Follow-ups to expect

• What if "*" can stand for any digit 1–9? (Same DP with multiplied counts.)
• How would you list every decoding? (Backtracking, output-sensitive time.)
• What if the answer is huge? (Return it modulo 10^9 + 7.)

In real software

Counting the ways to segment an unseparated stream (variable-length codes, word segmentation, parsing ambiguous tokens) uses the same last-piece recurrence.

Practice next