Decode Ways: DP String Decoding

You are given a string of digits. Each digit (or pair of digits) maps to a letter: 1 is A, 2 is B, all the way up to 26 for Z. Given a string like "226", how many ways can you decode it into letters?

This is LeetCode 91: Decode Ways, and it is one of the best problems for learning string decoding DP. If you have worked through Climbing Stairs, the structure will feel familiar. The twist here is that not every digit combination is valid, and zeros throw a wrench into the logic.

Why this problem matters

Decode ways LeetCode teaches you to apply the same linear DP skeleton from Climbing Stairs to a problem with conditional transitions. In Climbing Stairs, you always add the two previous values. Here, you only add them when the digits actually form valid codes.

That conditional logic is what makes this problem tricky. You have to think carefully about which digit combinations are allowed before you can set up the recurrence. Once you get that right, the DP itself is straightforward.

The string decoding DP pattern shows up in:

• Decode Ways II (LeetCode 639): same structure with wildcards
• Number of ways to form a string type problems
• Any problem where you parse a sequence and choose how many elements to consume at each step

The mapping rules

Before writing any code, let's be clear about what is valid:

• Single digit: 1 through 9 each map to a letter (A through I). The digit 0 by itself is not valid. There is no letter for zero.
• Two digits: 10 through 26 each map to a letter (J through Z). Anything 27 or higher is not valid as a two-digit code. And 00, 01 through 09 are not valid two-digit codes either.

This is where most people trip up. Zeros cannot stand alone and can only appear as the second digit in 10 or 20. If you see a 0 that is not part of 10 or 20, that substring has zero valid decodings.

Thinking it through

At each position in the string, you have up to two choices:

1. Take one digit. If the current digit is 1-9, it maps to a letter. The number of decodings from here equals the number of decodings of the remaining string after this digit.
2. Take two digits. If the current digit and the next digit together form a number between 10 and 26, that pair maps to a letter. The number of decodings from here equals the number of decodings of the remaining string after these two digits.

If the current digit is 0, neither option works. Zero alone is not a valid code, and no valid two-digit code starts with 0. That position contributes zero decodings.

The total at each position is the sum of whichever options are valid. That gives us the recurrence:

dp[i] = (if s[i-1] != '0': dp[i-1]) + (if 10 <= int(s[i-2:i]) <= 26: dp[i-2])

Starting with recursion

The most direct approach: try both options at each position and count the total.

def numDecodings(s):
    def helper(i):
        if i == len(s):
            return 1  # decoded everything, that is one valid way
        if s[i] == '0':
            return 0  # no letter for 0, dead end

        # Option 1: take one digit
        ways = helper(i + 1)

        # Option 2: take two digits (if valid)
        if i + 1 < len(s) and int(s[i:i+2]) <= 26:
            ways += helper(i + 2)

        return ways

    return helper(0)

This works but it is exponential. For a string like "111111111111", the recursion tree branches at every position, giving O(2^n) time. You can see the overlapping subproblems in the tree diagram above: the same suffixes get decoded over and over.

Adding memoization (top-down DP)

Cache each index so you never solve it twice.

def numDecodings(s):
    memo = {}

    def helper(i):
        if i == len(s):
            return 1
        if s[i] == '0':
            return 0
        if i in memo:
            return memo[i]

        ways = helper(i + 1)
        if i + 1 < len(s) and int(s[i:i+2]) <= 26:
            ways += helper(i + 2)

        memo[i] = ways
        return ways

    return helper(0)

Each index from 0 to n is computed once. Time: O(n). Space: O(n) for the memo plus O(n) for the call stack. Much better, but we can drop the recursion.

Building the DP array (bottom-up)

Define dp[i] as the number of ways to decode the first i characters of the string. We iterate forward and fill the table.

The base case: dp[0] = 1. An empty string has exactly one decoding (decode nothing). This might feel weird, but it is the standard base case for counting problems. Without it, the recurrence has nothing to build on.

For each position i from 1 to n:

• If the single digit s[i-1] is not '0', add dp[i-1] (one-digit decode is valid).
• If the two-digit number formed by s[i-2:i] is between 10 and 26, add dp[i-2] (two-digit decode is valid).

Let's walk through s = "226":

Each step checks: is the one-digit decode valid? Is the two-digit decode valid? Add the paths that work.

def numDecodings(s):
    if not s:
        return 0

    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # base case: empty string

    for i in range(1, n + 1):
        # One-digit decode
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]

        # Two-digit decode
        if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
            dp[i] += dp[i - 2]

    return dp[n]

Time: O(n). One pass through the string.

Space: O(n). The dp array.

Optimizing to O(1) space

Look at the recurrence: dp[i] only depends on dp[i-1] and dp[i-2]. Same as Climbing Stairs and House Robber. Two variables are all you need.

def numDecodings(s):
    if not s or s[0] == '0':
        return 0

    prev2 = 1  # dp[i-2], starts as dp[0]
    prev1 = 1  # dp[i-1], starts as dp[1]

    for i in range(2, len(s) + 1):
        current = 0

        # One-digit decode
        if s[i - 1] != '0':
            current += prev1

        # Two-digit decode
        if 10 <= int(s[i - 2:i]) <= 26:
            current += prev2

        prev2 = prev1
        prev1 = current

    return prev1

Same O(n) time, now O(1) space. Two variables sliding through the string, just like every other linear DP with constant state.

Let's trace through "226":

• Start: prev2 = 1, prev1 = 1
• i=2, digits "22": s[1]='2' != '0', so current += prev1 = 1. int("22")=22, valid, so current += prev2 = 1. current = 2. Shift: prev2 = 1, prev1 = 2
• i=3, digits "26": s[2]='6' != '0', so current += prev1 = 2. int("26")=26, valid, so current += prev2 = 1. current = 3. Shift: prev2 = 2, prev1 = 3
• Return prev1 = 3

The zero edge case in detail

Let's trace through "206" to see how zeros affect the DP:

• dp[0] = 1 (base)
• i=1, digit "2": not zero, so dp[1] = dp[0] = 1
• i=2, digit "0": it is zero, so no one-digit decode. Check two digits: int("20") = 20, which is valid (10-26), so dp[2] = dp[0] = 1
• i=3, digit "6": not zero, so dp[3] += dp[2] = 1. Check two digits: int("06") = 6, which is less than 10, so no two-digit decode. dp[3] = 1
• Answer: 1. The only valid decoding is "20" + "6" = T, F.

Now try "230":

• dp[0] = 1, dp[1] = 1
• i=2, digit "3": dp[2] += dp[1] = 1. Two digits "23" = 23, valid: dp[2] += dp[0] = 1. dp[2] = 2
• i=3, digit "0": zero, no one-digit decode. Two digits "30" = 30, which is > 26, so no two-digit decode either. dp[3] = 0
• Answer: 0. There is no valid decoding because "30" cannot be decoded.

And "30" by itself returns 0 too. The zero is stranded with no valid pair to absorb it.

Complexity analysis

The progression follows the same four-step pipeline as every linear DP problem:

1. Write the recursive solution to get the logic right.
2. Add memoization to eliminate redundant work.
3. Convert to bottom-up to remove recursion overhead.
4. Optimize space by keeping only what the recurrence needs.

Edge cases to watch for

• String starts with "0": return 0 immediately. No valid decoding can start with zero.
• Empty string: return 0 (or 1, depending on the problem statement; LeetCode says s.length is at least 1, so this rarely comes up).
• All ones and twos like "1111": maximum branching, similar to Climbing Stairs. Answer grows like Fibonacci.
• Zeros in the middle like "1001": the "00" kills it. dp at that position becomes 0, and everything after it stays 0. Answer: 0.
• Trailing zero like "10": only one decoding (J). The zero forces you to use the two-digit code.
• Single digit: "5" returns 1, "0" returns 0.

The building blocks

This problem is built on linear DP with constant state, the same fundamental pattern as Climbing Stairs and House Robber. You iterate through a sequence, and at each position you compute a value that depends on a fixed number of previous values.

The structure:

• State: dp[i] = number of ways to decode the first i characters
• Transition: add dp[i-1] if the single digit is valid, add dp[i-2] if the two-digit pair is valid
• Space optimization: since you only look back two steps, replace the array with two variables

What makes Decode Ways interesting compared to Climbing Stairs is the conditional transition. In Climbing Stairs, both lookbacks always apply. Here, each lookback only applies when the digit(s) form a valid code. That conditional logic, especially the zero handling, is the entire challenge of this problem.

The same building block appears in:

• Decode Ways II (LeetCode 639): same recurrence with wildcards (* can be any digit 1-9), requiring you to multiply counts
• Climbing Stairs (LeetCode 70): the simplified version where both transitions always fire
• House Robber (LeetCode 198): same two-variable lookback, but with a max decision instead of addition

Once you internalize linear DP with constant state as a reusable building block, these problems are all variations on the same theme.

From understanding to recall

You have just read through four versions of the solution, and the string decoding DP pattern probably makes sense right now. But will you be able to write the zero-handling logic from scratch next week? What about in an interview when you are working through LeetCode 91 under pressure?

Understanding and recall are different skills. Spaced repetition bridges the gap. You revisit the decode ways recurrence at increasing intervals, write it from scratch each time, and after a few reps the conditional transitions and zero edge cases become automatic. No more second-guessing whether "06" counts as a valid two-digit code (it does not).

The linear DP with constant state pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Climbing Stairs - Your first DP problem, same building block with unconditional transitions (no zero handling needed)
• House Robber - Same two-variable lookback, but with a max decision instead of summing paths