Decode Ways

The recurrence resembles Fibonacci, but zeros can remove transitions entirely. Derive the valid-token transitions first; the dynamic program then follows directly.

Recognize the partition pattern

You are given a string of digits and must count its complete partitions into codes from 1 through 26:

• A one-digit code is valid for 1 through 9.
• A two-digit code is valid for 10 through 26.
• A code cannot have a leading zero.
• Return 0 when no complete partition exists.

For example, "226" has three valid partitions:

2 | 2 | 6
2 | 26
22 | 6

The useful signal is structural:

1. The input is a sequence.
2. Each token has bounded length: one or two characters.
3. Token validity depends only on the characters inside that token.
4. We are counting valid partitions.

That combination points to one-dimensional dynamic programming. Build the string from left to right, count valid ways to form each prefix, and let invalid tokens contribute nothing.

The main trap is zero. A nonzero digit can stand alone, but 0 cannot. "10" and "20" are valid pairs; "01", "06", and "00" are not. Zero handling belongs inside the recurrence, not in a separate patch after the count is computed.

Use the decision tree to derive the state

At any position, there are at most two choices:

• consume one digit if it forms a valid code;
• consume two digits if they form a value from 10 through 26.

For "226", the choices are:

226
├── 2, then decode 26
│   ├── 2, then 6
│   └── 26
└── 22, then decode 6

There are three leaves, matching the three valid partitions.

A direct recursive solution follows this tree, but different branches repeatedly reach the same suffix. Dynamic programming merges those repeated subproblems by storing the number of ways for each prefix once.

The state should describe a complete obligation:

dp[i] = number of valid decodings of s[0:i]

The slice s[0:i] contains the first i characters, so:

• dp[0] describes the empty prefix;
• dp[1] describes the first character;
• dp[n] describes the entire input.

This is a prefix state, which makes the final answer dp[n].

Initialize the empty prefix correctly

Set:

dp[0] = 1

The empty prefix has one neutral way to begin. It does not represent a decoded letter. It represents the starting point from which the first valid token can be attached.

For example:

• a valid first one-digit token contributes dp[0];
• a valid first two-digit token also contributes dp[0].

If dp[0] were 0, every valid decoding beginning at the first character would incorrectly contribute zero.

Initialize all other entries to zero. Each later dp[i] will receive contributions only from valid tokens that end at position i.

Derive the transitions from the final token

Consider a prefix ending at position i. Its final token can have only one of two lengths.

One-digit transition

The final character is s[i - 1]. It can stand alone when it is not zero:

if s[i - 1] != "0":
    dp[i] += dp[i - 1]

Every valid decoding of the first i - 1 characters can be extended with this one-digit token.

A zero contributes nothing through this transition because "0" has no mapping.

Two-digit transition

The final pair is s[i - 2:i]. It can be one token only when its value lies between 10 and 26:

if i >= 2:
    two_digit = int(s[i - 2:i])
    if 10 <= two_digit <= 26:
        dp[i] += dp[i - 2]

The count comes from dp[i - 2] because every valid decoding of the preceding prefix can be extended by this two-digit token.

The numeric range automatically rejects:

• "06" and "01" because they are below 10;
• "27" and larger pairs because they exceed 26;
• "00" because it is below 10.

The complete recurrence is:

[ dp[i] = \text{valid_one}(i)\cdot dp[i-1] + \text{valid_two}(i)\cdot dp[i-2] ]

where each validity condition either permits its contribution or contributes zero.

Zeros are not exceptions bolted onto a Fibonacci recurrence. They are failed transitions in the same recurrence.

That distinction matters. "10" works because the zero participates in a valid pair. "06" fails because the zero cannot start a valid token and the pair has a leading zero.

Prove the recurrence by the final token

Assume dp[j] correctly counts every prefix shorter than i. Consider any valid decoding of s[0:i].

Its final token must be one of the following:

1. A one-character token.
   The final character is from 1 through 9. Removing it leaves a valid decoding of s[0:i-1]. There are exactly dp[i - 1] such decodings.

2. A two-character token.
   The final pair is a value from 10 through 26. Removing it leaves a valid decoding of s[0:i-2]. There are exactly dp[i - 2] such decodings.

These groups are disjoint: the final characters cannot simultaneously be used as both a one-character and a two-character token. They are exhaustive because valid tokens have no other lengths.

If the final one-digit token is invalid, the first group contributes zero. If the final pair is invalid, the second group contributes zero. Adding the valid contributions therefore counts every decoding exactly once.

The base case dp[0] = 1 supplies the neutral starting state. By induction, every dp[i] is correct, so dp[n] counts exactly the complete decodings of the input.

The invariant to keep in your head is:

After computing dp[i], it counts complete valid tokenizations of s[0:i]—not partial attempts and not paths waiting for an unresolved zero.

Dry-run the ambiguous and invalid cases

Ambiguous input: "226"

i	Prefix	One-digit contribution	Two-digit contribution	dp[i]
0	""	—	—	1
1	2	dp[0] = 1	—	1
2	22	dp[1] = 1	dp[0] = 1	2
3	226	dp[2] = 2	dp[1] = 1	3

At i = 3:

• the final 6 extends the two decodings of "22";
• the final 26 extends the one decoding of "2".

Therefore:

dp[3] = 2 + 1 = 3

Leading zero: "06"

i	Prefix	One-digit result	Two-digit result	dp[i]
0	""	—	—	1
1	0	invalid	—	0
2	06	6 is valid, but dp[1] = 0	"06" invalid	0

The 6 is valid by itself, but it cannot rescue the preceding impossible prefix. A valid final token still produces zero ways when the prefix before it has zero ways.

Dead suffix: "100"

Compute the prefixes:

• dp[0] = 1
• dp[1] = 1 because "1" is valid
• dp[2] = 1 because "10" is valid
• dp[3] = 0 because the final "0" cannot stand alone and "00" is not valid

The earlier pair "10" is valid, but it does not make the later suffix decodable. Dynamic programming exposes that failure at the exact prefix where it occurs.

The same reasoning handles "11106":

• "10" can consume the zero;
• "06" cannot;
• the valid complete partitions are 1 | 1 | 10 | 6 and 11 | 10 | 6.

The recurrence does not need a special case for this example. It simply rejects the invalid transition.

Implement the bottom-up solution in Python

The table implementation mirrors the derivation directly:

def num_decodings(s: str) -> int:
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        # Use s[i - 1] as a one-digit code.
        if s[i - 1] != "0":
            dp[i] += dp[i - 1]

        # Use s[i - 2:i] as a two-digit code.
        if i >= 2:
            two_digit = int(s[i - 2:i])
            if 10 <= two_digit <= 26:
                dp[i] += dp[i - 2]

    return dp[n]

Every line has a corresponding proof obligation:

• dp[i] counts the first i characters.
• dp[0] = 1 represents the neutral empty prefix.
• A nonzero final character inherits dp[i - 1].
• A valid two-digit suffix inherits dp[i - 2].
• Invalid tokens add nothing.
• dp[n] is the count for the complete string.

Under interview pressure, I would start with this version. The table is inspectable: when a test fails, print dp and find the first prefix whose count violates the invariant. That is usually more valuable than saving a few variables.

The pair check can also avoid integer conversion:

def num_decodings(s: str) -> int:
    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 (
            s[i - 2] == "1"
            or (s[i - 2] == "2" and s[i - 1] <= "6")
        ):
            dp[i] += dp[i - 2]

    return dp[n]

The first version is often easier to audit because the valid numeric range is visible. The second makes the leading-digit rule explicit. Both implement the same recurrence.

Compress the state only after the invariant is clear

Each dp[i] uses only dp[i - 1] and dp[i - 2], so the table can be compressed to constant auxiliary space.

Because the input length is at least one, initialize the first two prefix states explicitly:

def num_decodings_optimized(s: str) -> int:
    # dp[0] represents the empty prefix.
    prev_two = 1

    # Compute dp[1].
    prev_one = 1 if s[0] != "0" else 0

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

        # Final character s[i - 1] used alone.
        if s[i - 1] != "0":
            current += prev_one

        # Final pair s[i - 2:i] used as one code.
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:
            current += prev_two

        # Prepare for the next prefix.
        prev_two, prev_one = prev_one, current

    return prev_one

At the start of each loop iteration:

prev_two = dp[i - 2]
prev_one = dp[i - 1]

After computing current = dp[i], shift the values forward. That is the entire optimization. If the variable mapping cannot be stated this plainly, the table is the better implementation.

Complexity and boundary tests

For the table solution:

• Time: O(n)
• Space: O(n)

For the rolling-state solution:

• Time: O(n)
• Auxiliary space: O(1)

The answer is guaranteed to fit in a 32-bit integer, so no special arithmetic technique is required.

Test the transition boundaries rather than only ordinary examples:

Input	Expected	What it checks
"7"	1	Single valid digit
"0"	0	Zero cannot stand alone
"10"	1	Valid zero pair
"20"	1	Another valid zero pair
"26"	2	One-digit and two-digit choices
"27"	1	Pair exceeds 26; only `2
"06"	0	Leading-zero pair and dead prefix
"111"	3	Repeated ambiguity
"100"	0	Valid 10 followed by an impossible suffix

Common failures are predictable:

• Setting dp[0] = 0, which kills every valid first token.
• Accepting every nonzero pair, which incorrectly allows "27" or "99".
• Treating "01" or "06" as valid because their numeric values are small.
• Checking a two-character slice before confirming i >= 2.
• Returning immediately when seeing a zero, which incorrectly rejects valid pairs such as "10".
• Compressing the state before assigning a precise meaning to each rolling variable.

The transferable recognition rule

When a sequence must be partitioned into valid tokens of bounded length:

1. Define a prefix state.
2. Set the empty prefix to one neutral way.
3. Classify every valid token that can end at the current position.
4. Add the number of ways to reach the prefix before that token.
5. Let invalid tokens contribute zero.

For Decode Ways, the token lengths are one and two, and zeros simply remove invalid transitions. That is the pattern to carry into the next problem: do not memorize a Fibonacci-looking formula. Name the prefix, inspect the possible final tokens, and let the validity rules determine the recurrence.