Decode Ways

Decode Ways is a classic 1-D dynamic-programming problem. It looks like a string-parsing puzzle, but underneath it is the same shape as counting staircase paths: each position can be reached one or two steps back.

The slow way first

The brute-force idea: at each position, branch — take one digit, or take two digits if they form 10..26 — and recurse on the rest. That explores a binary tree of choices, which is exponential (roughly O(2ⁿ)). Many of those recursive calls re-solve the exact same suffix over and over.

The question to ask: what does the answer for the first i characters depend on? Only the answers for the first i-1 and first i-2 characters. That overlap is the signal to use dynamic programming.

The idea: build dp left to right

Let dp[i] be the number of ways to decode the first i characters of s. Then:

• If the single digit s[i-1] is 1..9 (not 0), those decodings extend every decoding of the first i-1 chars, so add dp[i-1].
• If the pair s[i-2:i] is 10..26, that letter extends every decoding of the first i-2 chars, so add dp[i-2].

The base case is dp[0] = 1: the empty prefix has one decoding.

The key insight: it is the Fibonacci / climbing-stairs recurrence with two validity gates — a digit must avoid a leading zero, and a pair must land in 10..26.

Walk through it

Step through the animation. The pointer i walks the dp array. At each i we check the one-digit window, then the two-digit window, adding the matching earlier dp value. For s = '226': dp = [1, 1, 2, 3], so the answer is dp[3] = 3.

Pseudocode

n = length of s
dp = array of zeros, length n + 1
dp[0] = 1                              # empty prefix: one way
for i from 1 to n:
    if s[i-1] is not '0':
        dp[i] += dp[i-1]               # take one digit (1..9)
    if i >= 2 and s[i-2:i] is in 10..26:
        dp[i] += dp[i-2]               # take a two-digit pair
return dp[n]

The Python solution

def num_decodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]
        if i >= 2 and '10' <= s[i - 2:i] <= '26':
            dp[i] += dp[i - 2]
    return dp[n]

• dp[i] is the number of decodings of the first i characters; dp has length n + 1.
• dp[0] = 1 is the base case — the empty string decodes exactly one way.
• The single-digit check s[i-1] != '0' rejects a leading zero (0 maps to no letter on its own).
• The two-digit check uses string comparison: '10' <= s[i-2:i] <= '26' is true exactly for valid pairs, and it naturally excludes things like '06'.
• We add, not replace — a position can be reachable by both a single digit and a pair, so we sum both contributions.

Complexity

We trade O(n) extra space for the dp array to collapse an exponential search into a single linear pass. (You can even drop to O(1) space by keeping just the last two values.)

When this pattern shows up

Practice