Decode Ways

Memoized recursion — try one digit and two

Memoization saves a subproblem's answer the first time you solve it, then reuses that answer on later visits. It's a top-down form of dynamic programming (DP), where smaller saved answers build the final result. Define ways(i) as the number of decodings for the suffix beginning at index i.

If s[i] is 0, that suffix contributes no decoding. Otherwise, consume one digit. When s[i:i + 2] is from 10 through 26, consume two as a second choice. The transition — the rule that combines those smaller answers — is:

ways(i) = ways(i + 1) + ways(i + 2)

The second term exists only when the two-digit code is valid.

def num_decodings(s: str) -> int:
    memo: dict[int, int] = {}
 
    def ways(index: int) -> int:
        if index == len(s):
            return 1
        if s[index] == "0":
            return 0
        if index in memo:
            return memo[index]
 
        total = ways(index + 1)
        if index + 1 < len(s) and 10 <= int(s[index:index + 2]) <= 26:
            total += ways(index + 2)
        memo[index] = total
        return total
 
    return ways(0)

Each index is solved once, with constant work around its recursive calls. Time O(n). Space O(n) for the memo and recursion stack.

Rolling prefix DP — keep the last two counts

Scan prefixes from left to right. Let previous count decodings through the previous digit and two_back count decodings through the digit before that. For the current digit:

• If it isn't 0, add previous for the one-digit transition.
• If the last two digits form 10 through 26, add two_back for the two-digit transition.

def num_decodings(s: str) -> int:
    two_back = 1
    previous = 0 if s[0] == "0" else 1
 
    for i in range(1, len(s)):
        current = 0
        if s[i] != "0":
            current += previous
        if 10 <= int(s[i - 1:i + 1]) <= 26:
            current += two_back
        two_back, previous = previous, current
 
    return previous

This is the same DP with old prefix entries discarded as soon as nothing can read them. Time O(n). Space O(1).