LeetCode 91: Decode Ways

Problem Restatement

We are given a string s containing only digits.

The digits encode letters using this mapping:

"A" -> "1"
"B" -> "2"
...
"Z" -> "26"

We need to count how many different ways the string can be decoded.

A digit group is valid only if it maps to a number from 1 to 26.

So:

"12"

can be decoded as:

"1" "2" -> "AB"
"12"    -> "L"

The answer is 2.

The official constraints are 1 <= s.length <= 100, s contains only digits, and it may contain leading zeroes. The answer fits in a 32-bit integer.

Input and Output

Function shape:

class Solution:
    def numDecodings(self, s: str) -> int:
        ...

Examples

Example 1:

s = "12"

Valid decodings:

"1" "2" -> "AB"
"12"    -> "L"

Answer:

2

Example 2:

s = "226"

Valid decodings:

"2" "2" "6" -> "BBF"
"22" "6"    -> "VF"
"2" "26"    -> "BZ"

Answer:

3

Example 3:

s = "06"

This is invalid.

"0" does not map to any letter.

"06" is also invalid because it has a leading zero.

Answer:

0

First Thought: Recursion

At each index, we have at most two choices.

We can take one digit if it is between "1" and "9".

We can take two digits if they form a number between "10" and "26".

So from index i, the answer is:

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

but only when those one-digit and two-digit choices are valid.

A direct recursive solution works logically, but it repeats the same suffix many times.

For example, in "226", both paths may ask how many ways exist for the suffix starting at the last character.

This repeated work suggests dynamic programming.

Key Insight

Let:

dp[i]

mean:

the number of ways to decode s[:i]

So dp[0] means the empty prefix.

We set:

dp[0] = 1

This does not mean the empty string is an answer. It means there is one neutral way to decode nothing, so later valid choices can build from it.

For each position i, we consider the last one digit and the last two digits.

For prefix s[:i], the last one digit is:

s[i - 1]

The last two digits are:

s[i - 2:i]

Transition

If the last one digit is valid, then it can stand alone.

That means every decoding of s[:i - 1] can be extended by this one digit.

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

If the last two digits form a valid number from 10 to 26, then every decoding of s[:i - 2] can be extended by this two-digit letter.

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

The valid two-digit check starts at 10, so strings like "06" are rejected.

Algorithm

Create an array:

dp = [0] * (len(s) + 1)

Set:

dp[0] = 1

Then loop:

i = 1, 2, ..., len(s)

At each i:

1. If s[i - 1] is not "0", add dp[i - 1].
2. If i >= 2 and s[i - 2:i] is between "10" and "26", add dp[i - 2].
3. Return dp[len(s)].

Walkthrough

Use:

s = "226"

Create:

dp = [1, 0, 0, 0]

At i = 1, prefix is:

"2"

Single digit "2" is valid.

dp[1] += dp[0]

Now:

dp = [1, 1, 0, 0]

At i = 2, prefix is:

"22"

Single digit "2" is valid, so add dp[1].

Two digits "22" are valid, so add dp[0].

dp[2] = 2

Now:

dp = [1, 1, 2, 0]

At i = 3, prefix is:

"226"

Single digit "6" is valid, so add dp[2].

Two digits "26" are valid, so add dp[1].

dp[3] = 3

Final answer:

3

Handling Zero

Zero is the main edge case.

A single "0" is invalid.

"0" -> 0 ways

But "10" and "20" are valid:

"10" -> "J"
"20" -> "T"

Other combinations ending in zero may be invalid:

"30" -> invalid
"00" -> invalid
"06" -> invalid

The DP rules handle all of these.

For "10":

"0" cannot stand alone
"10" is valid

so the answer comes from dp[i - 2].

For "30":

"0" cannot stand alone
"30" is not between 10 and 26

so the answer becomes 0.

Correctness

The algorithm counts decodings by the final digit group of each valid decoding.

For a prefix s[:i], any valid decoding must end in either a one-digit group or a two-digit group, because the mapping only covers numbers from 1 to 26.

If the decoding ends with one digit, that last digit must be from "1" to "9". Removing it leaves a valid decoding of s[:i - 1]. The algorithm adds exactly dp[i - 1] for this case.

If the decoding ends with two digits, those digits must form a number from 10 to 26. Removing them leaves a valid decoding of s[:i - 2]. The algorithm adds exactly dp[i - 2] for this case.

These two cases are disjoint because a decoding cannot end with both a one-digit group and a two-digit group at the same time.

The algorithm considers both possible final group sizes and only accepts valid groups. Therefore, dp[i] equals the number of valid decodings of s[:i].

By induction over i, the final value dp[len(s)] is the number of valid decodings of the whole string.

Complexity

Let:

n = len(s)

Implementation

class Solution:
    def numDecodings(self, 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 10 <= int(s[i - 2:i]) <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

Code Explanation

Create the DP array:

dp = [0] * (n + 1)

Set the base case:

dp[0] = 1

For each prefix length i:

for i in range(1, n + 1):

Check whether the final one digit can be decoded:

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

Check whether the final two digits can be decoded:

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

Return the number of ways for the full string:

return dp[n]

Space-Optimized Implementation

Since dp[i] only depends on dp[i - 1] and dp[i - 2], we can keep two variables.

class Solution:
    def numDecodings(self, s: str) -> int:
        prev2 = 1
        prev1 = 0

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

            if s[i - 1] != "0":
                cur += prev1 if i > 1 else prev2

            if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
                cur += prev2

            prev2, prev1 = prev1, cur

        return prev1

A cleaner version initializes prev1 as the answer for the first character:

class Solution:
    def numDecodings(self, s: str) -> int:
        prev2 = 1
        prev1 = 0 if s[0] == "0" else 1

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

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

            if 10 <= int(s[i - 2:i]) <= 26:
                cur += prev2

            prev2, prev1 = prev1, cur

        return prev1

Space complexity becomes:

Testing

def run_tests():
    s = Solution()

    assert s.numDecodings("12") == 2
    assert s.numDecodings("226") == 3
    assert s.numDecodings("06") == 0

    assert s.numDecodings("0") == 0
    assert s.numDecodings("10") == 1
    assert s.numDecodings("20") == 1
    assert s.numDecodings("30") == 0
    assert s.numDecodings("100") == 0
    assert s.numDecodings("101") == 1
    assert s.numDecodings("11106") == 2
    assert s.numDecodings("27") == 1

    print("all tests passed")

run_tests()

Test meaning: