Decode Ways Explained: Tracing 226, 06, and 10

Imagine you are handed a numerical cipher where 1 represents A all the way to 26 representing Z. Your task is to figure out how many valid English word-prefix combinations can be formed from a sequence of digits. Consider our working example: the string s = "226".

At first glance, you might think you can just eyeball the pieces. You could slice it into single digits: 2, 2, and 6, which map to B, B, and F. Or you could group the first two digits together: 22 and 6, mapping to V and F. Or maybe group the last two: 2 and 26, mapping to B and Z. That gives us 3 distinct ways to decode "226".

Simple enough for three digits, right? But what happens when we look at strings that contain zeros, like s = "06" or s = "10"? In "06", the leading zero ruins the first character because there is no letter corresponding to 0. In "10", the zero cannot stand alone either—it must combine with the preceding 1 to form 10 (J), meaning 1 and 0 cannot be split into 1 and 0 (A and nothing).

If you try to write a brute-force recursive function that branches at every single step—deciding whether to take one digit or two digits—you will quickly find yourself recalculating the exact same suffixes over and over again. For a string of length $n$, naive branching leads to $O(2^n)$ time complexity. Without a systematic way to track subproblem states, even a modest string will melt your call stack.

When we look at our working example $s=\text{"226"}$, we are really asking: at each position in the string, do we consume a single digit like 2 (mapping to B), or do we pair it with the next digit like 22 (mapping to V)? This dual-choice structure turns string decoding into a step-by-step decision tree.

Imagine standing at the start of $s=\text{"226"}$. Your first choice is either to take the single digit 2 and leave "26" to be decoded, or to take the double digit 22 and leave "6" to be decoded. If you take 2, you branch into all valid decodings of "26". If you take 22, you branch into all valid decodings of "6".

This overlapping substructure means that naive recursion will recompute the same suffixes over and over. To build a robust mental model, we map each index $i$ of the string to a subproblem: how many valid decodings exist for the prefix of length $i$?

Let us formalize the transition at index $i$:
- Single-digit check: If the character at $s[i-1]$ is not $\text{’0’}$, it can be decoded on its own, contributing the decodings from $i-1$.
- Double-digit check: If the two-character slice $s[i-\mathrm{2..}i-1]$ forms a valid number between 10 and 26 inclusive, it can be decoded as a pair, contributing the decodings from $i-2$.

When we test this model on our second target $s=\text{"06"}$, the first digit is $\text{’0’}$, failing the single-digit check, and "06" is not a valid 10-26 pair, yielding 0 decodings immediately. For $s=\text{"10"}$, the single digit $\text{’1’}$ is valid but cannot stand alone if followed by $\text{’0’}$ unless paired, whereas the pair "10" is valid ($10=\text{’J’}$), giving us exactly 1 way.

Now we put the dynamic programming recurrence into motion using our locked examples: s = "226", s = "06", and s = "10". We will maintain a DP array where dp[i] represents the number of valid ways to decode the prefix of length i.

Given

- Target string 1: s = "226"
- Target string 2: s = "06"
- Target string 3: s = "10"

For s = "226" (length $n=3$):
- Base cases: dp[0] = 1 (empty string has 1 way), and for $i=1$, dp[1] = 1 because s[0] = '2' is non-zero.
- Step $i=2$ (string prefix "22"):
- Single-digit check: s[1] = '2' is non-zero, so add dp[1] (1).
- Double-digit check: substring "22" is between 10 and 26, so add dp[0] (1).
- Result: dp[2] = 1 + 1 = 2 (decodings: 2|2 and 22).
- Step $i=3$ (string prefix "226"):
- Single-digit check: s[2] = '6' is non-zero, so add dp[2] (2).
- Double-digit check: substring "26" is between 10 and 26, so add dp[1] (1).
- Result: dp[3] = 2 + 1 = 3.

For s = "06":
- Base case: dp[0] = 1.
- Step $i=1$ (prefix "0"):
- Single-digit check: s[0] = '0' is zero, so do not add dp[0]. Double-digit check: $i=1$ has no previous character.
- Result: dp[1] = 0.
- Step $i=2$ (prefix "06"):
- dp[2] depends on dp[1] (which is 0) and valid double digits. Because the prefix starts with a zero, all paths fail immediately.
- Result: dp[2] = 0.

For s = "10":
- Base cases: dp[0] = 1, dp[1] = 1 ('1' is non-zero).
- Step $i=2$ (prefix "10"):
- Single-digit check: s[1] = '0' is zero, so we cannot add dp[1]. (A zero cannot stand alone as A-Z).
- Double-digit check: substring "10" is valid ($10\le 10\le 26$), so we add dp[0] (1).
- Result: dp[2] = 0 + 1 = 1 (decoding: 10 only).

Result

- "226" $\to 3$ ways (2|2|6, 22|6, 2|26).
- "06" $\to 0$ ways.
- "10" $\to 1$ way (10).

def numDecodings(s: str) -> int:
    if not s or s[0] == '0':
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    
    for i in range(2, n + 1):
        # TODO: Implement single-digit and double-digit transitions here
        pass
    return dp[n]

Now that we have traced s = "226", s = "06", and s = "10", let us apply the exact same recurrence logic to a new input string: s = "30".

Recall the two rules from our DP model:
- A single digit adds dp[i-1] decodings only if it is non-zero (1 to 9).
- A two-digit pair adds dp[i-2] decodings only if it forms a valid number between 10 and 26.

Using these rules, trace out the values of the DP array for s = "30" from left to right, starting with dp[0] = 1, dp[1] = 0 (since s[0] = '3'), and compute the final output.

s = "30"
# Compute dp table for s = "30"
# dp[0] = 1
# dp[1] = ?
# dp[2] = ?

Now that you have traced 226, 06, 10, and handled the dangerous trap of 30, you possess a reusable mental model for bounded sequence-partitioning. The core lesson from the Decode Ways problem is not just alphabet substitution; it is how local validation constraints (1..26) interact with sequential choices of length 1 or length 2. When you encounter a new string processing challenge where elements can be consumed individually or paired up subject to validity rules, you can directly lift this dynamic programming state machine.

Consider a modified scenario: suppose you are decoding a stream of digits where a single digit maps to a valid symbol only if it is odd, and a two-digit pair maps to a valid symbol only if it falls between 11 and 39. The state update rule remains identical in spirit:

$$\text{dp}[i]=\{\begin{array}{ll}\text{dp}[i-1]& \text{if single element is valid}\\ 0& \text{otherwise}\end{array}+\{\begin{array}{ll}\text{dp}[i-2]& \text{if pair is valid}\\ 0& \text{otherwise}\end{array}$|

By keeping track of just the last two subproblem states ($\text{dp}[i-1]$ and $\text{dp}[i-2]$), you compress an exponential branching recursion into an $O(n)$ time and $O(1)$ space scan. Whenever local constraints restrict lookaheads of width $k$, look for a recurrence relation summing over sliding window histories.