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'.

Small length, so O(n) is trivial to hit; the difficulty is entirely 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.

class Solution:
    def numDecodings(self, 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 the constraints kill it: at n = 100 a doubly-branching recursion is ~2^100 calls, recomputing each suffix count exponentially often.

Approach 2 — Top-down memoization

The insight: only n + 1 suffixes exist; cache ways(i).

from functools import cache

class Solution:
    def numDecodings(self, 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.

class Solution:
    def numDecodings(self, 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].

class Solution:
    def numDecodings(self, 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.