Decode Ways

Problem

A message of letters A–Z was encoded to digits using the mapping A → "1", B → "2", …, Z → "26". Given a string of digits s, count how many distinct original letter strings could have produced it.

To decode, s is split into groups, each group being either one digit (1–9) or two digits forming a value 10–26. A group with a leading zero (like "06") is invalid, and a lone "0" decodes to nothing.

Return the number of valid decodings (which may be 0).

Examples

• s = "12" → 2 — "1 2" → "AB" or "12" → "L".
• s = "226" → 3 — "2 2 6" (BBF), "22 6" (VF), "2 26" (BZ).
• s = "06" → 0 — no group can start with 0, and "06" is not a valid two-digit code.

Constraints

• 1 <= s.length <= 100
• s consists of digits only and may contain '0'.

The length is small, so an O(n) solution is easy to reach. The difficulty is in the zero-handling edge cases, not performance.

Think about it first

TL;DR

1-D DP over the suffix index — add one-digit and two-digit continuations — collapsed to two rolling scalars: O(n) time, O(1) space.

The recurrence

Let n = len(s) and ways(i) = number of decodings of the suffix s[i:]:

ways(n)   = 1                              # empty suffix: exactly one decoding
ways(i)   = one + two, where
    one   = ways(i+1)   if s[i] != '0'                    else 0
    two   = ways(i+2)   if i+1 < n and 10 <= int(s[i:i+2]) <= 26   else 0
answer    = ways(0)

If both one and two are 0 (e.g. a stray '0'), that suffix contributes nothing and the total collapses to 0.

Approach 1 — Brute-force recursion

Branch on “take one digit” vs. “take two digits,” guarding validity.

def numDecodings(s: str) -> int:
    n = len(s)
    def ways(i: int) -> int:
        if i == n:
            return 1
        if s[i] == "0":
            return 0                          # no valid single or leading-zero double
        total = ways(i + 1)
        if i + 1 < n and 10 <= int(s[i:i + 2]) <= 26:
            total += ways(i + 2)
        return total
    return ways(0)

Complexity: O(2^n) time, O(n) stack.

Why it fails the constraints: at n = 100 the doubly-branching recursion makes on the order of 2^100 calls, recomputing the same suffix counts repeatedly. The recursion tree for s = "226" shows the duplication:

flowchart TD
    W0["ways(0)"] -->|take '2'| W1["ways(1)"]
    W0 -->|take '22'| W2a["ways(2)"]
    W1 -->|take '2'| W2b["ways(2)"]
    W1 -->|take '26'| W3a["ways(3) = 1"]
    W2a -->|take '6'| W3b["ways(3) = 1"]
    W2b -->|take '6'| W3c["ways(3) = 1"]

ways(2) is computed twice here, and the overlap grows exponentially with n.

Approach 2 — Top-down memoization

The insight: only n + 1 distinct suffixes exist, so cache ways(i) and compute each once.

from functools import cache

def numDecodings(s: str) -> int:
    n = len(s)
    @cache
    def ways(i: int) -> int:
        if i == n:
            return 1
        if s[i] == "0":
            return 0
        total = ways(i + 1)
        if i + 1 < n and 10 <= int(s[i:i + 2]) <= 26:
            total += ways(i + 2)
        return total
    return ways(0)

Complexity: O(n) time, O(n) space (cache + stack).

Approach 3 — Bottom-up tabulation

The insight: ways(i) depends on ways(i+1) and ways(i+2), so fill the table from the end backward.

def numDecodings(s: str) -> int:
    n = len(s)
    dp = [0] * (n + 2)
    dp[n] = 1                                 # empty suffix
    for i in range(n - 1, -1, -1):
        if s[i] == "0":
            dp[i] = 0
            continue
        dp[i] = dp[i + 1]
        if i + 1 < n and 10 <= int(s[i:i + 2]) <= 26:
            dp[i] += dp[i + 2]
    return dp[0]

Walkthrough (s = "226", n = 3), filling right to left:

• dp[3] = 1 (base)
• i=2 ('6'): dp[2] = dp[3] = 1 ("26" two-digit needs index 1, not here) → 1
• i=1 ('2'): dp[1] = dp[2] = 1; "26" is in 10..26 → add dp[3] = 1 → 2
• i=0 ('2'): dp[0] = dp[1] = 2; "22" is in 10..26 → add dp[2] = 1 → 3

Return dp[0] = 3.

Complexity: O(n) time, O(n) space.

Approach 4 — Space-optimized (two rolling scalars)

The insight: each cell reads only the next two, so keep ahead1 = dp[i+1] and ahead2 = dp[i+2].

def numDecodings(s: str) -> int:
    n = len(s)
    ahead2, ahead1 = 0, 1                     # dp[i+2], dp[i+1]; dp[n] = 1
    for i in range(n - 1, -1, -1):
        if s[i] == "0":
            curr = 0
        else:
            curr = ahead1
            if i + 1 < n and 10 <= int(s[i:i + 2]) <= 26:
                curr += ahead2
        ahead2, ahead1 = ahead1, curr
    return ahead1

Walkthrough (s = "12"): start (ahead2, ahead1) = (0, 1). i=1 ('2'): curr = ahead1 = 1 → shift to (1, 1). i=0 ('1'): curr = ahead1 = 1; "12" in range → + ahead2 = 1 → 2. Return 2.

Complexity: O(n) time, O(1) space.

Common pitfalls

• Treating '0' as decodable alone. '0' has no letter; a suffix starting at a '0' that isn’t the tail of 10/20 has 0 decodings.
• Two-digit range errors. Valid two-digit codes are 10–26 only. "27", "30", "09" are all invalid as pairs; forgetting the lower bound 10 wrongly accepts "01".
• Bounds on the two-digit read. Guard i + 1 < n before forming s[i:i+2]; at the last index there is no pair.
• Base case dp[n] = 1. The empty suffix has exactly one decoding; seeding it to 0 zeroes out every count.

Pattern takeaway

Decode Ways is Climbing Stairs with validity gates: the same f(i) = f(i+1) + f(i+2) shape, but each term is admitted only if its 1- or 2-character group forms a legal code. The reusable rule for string DP: define the state as an index into the string, split on how many characters the next token consumes, and guard each branch with the token’s validity condition — then collapse the fixed-width look-ahead to rolling scalars.