LeetCode 91 - Decode Ways

LeetCode Problem 91

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming

Solution

Problem Understanding

This problem asks us to determine how many different valid ways a numeric string can be decoded into letters using the mapping:

• "1" → 'A'
• "2" → 'B'
• ...
• "26" → 'Z'

The input is a string s containing only digits. Each digit or pair of digits may represent a letter if it forms a valid number between 1 and 26. Our task is to count the total number of valid decoding combinations for the entire string.

The key challenge is that multiple interpretations may exist. For example, "12" can be split into:

• "1" + "2" → "AB"
• "12" → "L"

So the answer is 2.

However, not every split is valid. The digit '0' creates complications because it cannot be decoded on its own. For example:

• "10" is valid because "10" maps to 'J'
• "20" is valid because "20" maps to 'T'
• "06" is invalid because "06" is not allowed, only "6" is valid

The expected output is the total number of valid ways to decode the entire string. If no valid decoding exists, we return 0.

The constraints are important:

• 1 <= s.length <= 100
• The answer fits in a 32-bit integer

A length of 100 is small enough that polynomial-time solutions are efficient, but large enough that exponential brute force would become impractical. This strongly suggests a dynamic programming solution.

Several edge cases deserve attention upfront. Strings beginning with '0' are immediately invalid because no letter maps to zero. Consecutive zeros or malformed combinations such as "30" and "100" can invalidate part or all of the decoding. Single-character strings also require careful handling because they may or may not be valid depending on whether the digit is zero.

Approaches

Brute Force Approach

A brute-force solution would recursively try every possible way to split the string.

At each position, we have up to two choices:

1. Decode one digit, if it forms a valid number from 1 to 9
2. Decode two digits, if they form a valid number from 10 to 26

For example, with "226":

• Take "2" → recurse on "26"
• Take "22" → recurse on "6"

This naturally forms a recursion tree where every valid split is explored.

The brute-force approach is correct because it systematically considers every possible decoding path and counts all valid outcomes. However, it performs a large amount of repeated work.

For instance, different recursive paths may repeatedly solve the same suffix of the string. In "1111", the substring "11" gets recalculated multiple times. This overlapping subproblem structure leads to exponential growth.

Since each position may branch into two recursive calls, the worst-case time complexity becomes exponential, approximately O(2^n), which is too slow for n = 100.

Key Insight for an Optimal Solution

The important observation is that the number of decoding ways for a position depends only on the decoding counts of later positions.

Suppose dp[i] represents the number of ways to decode the substring starting at index i.

At index i, we can:

• Use one digit, if s[i] != '0'
• Use two digits, if s[i:i+2] forms a valid number between 10 and 26

This leads to a recurrence:

dp[i] =
    dp[i+1]                    if one-digit decode is valid
  + dp[i+2]                    if two-digit decode is valid

Since each subproblem only depends on the next two positions, dynamic programming eliminates repeated computation and reduces the complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively explores all decoding possibilities, repeated work makes it inefficient
Optimal Dynamic Programming	O(n)	O(1)	Uses previous results to avoid recomputation

Algorithm Walkthrough

The optimal solution uses dynamic programming with constant space.

1. Handle invalid starting conditions.

If the string starts with '0', return 0 immediately. No valid decoding begins with zero. 2. Define the meaning of the DP state.

Let dp[i] represent the number of ways to decode the substring beginning at index i.

Since we only need the previous two states, we can optimize space and store just two variables instead of an entire array. 3. Initialize the base case.

We define:

• next1 = 1, representing dp[n]
• next2 = 0, representing dp[n+1]

The empty string has exactly one valid decoding, which helps naturally terminate recursion. 4. Traverse the string from right to left.

We process characters starting from the end because dp[i] depends on dp[i+1] and dp[i+2]. 5. Handle the current digit.

If s[i] == '0', there are zero ways to decode from this position because zero cannot stand alone.

Otherwise:

• Start with current = next1, meaning we decode one digit.

6. Check whether a two-digit decode is valid.

If i + 1 < n and the number formed by s[i:i+2] lies between 10 and 26, then add next2 to the current count. 7. Shift the variables.

After computing the current result:

• next2 = next1
• next1 = current

This prepares the values for the next iteration. 8. Return the result.

After processing the entire string, next1 contains the number of ways to decode the full string.

Why it works

The algorithm works because every valid decoding at index i must begin with either one valid digit or one valid two-digit number. These are the only possibilities allowed by the encoding rules.

The recurrence guarantees correctness because it counts all valid decompositions exactly once:

• dp[i+1] counts decodings after choosing one digit
• dp[i+2] counts decodings after choosing two digits

Since every valid path must start with one of these choices and invalid choices contribute zero, the dynamic programming state always represents the exact number of valid decodings for each suffix.

Python Solution

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)

        next_one = 1
        next_two = 0

        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                current = 0
            else:
                current = next_one

                if (
                    i + 1 < n
                    and (
                        s[i] == '1'
                        or (s[i] == '2' and s[i + 1] <= '6')
                    )
                ):
                    current += next_two

            next_two = next_one
            next_one = current

        return next_one

The implementation processes the string from right to left. This direction is important because each position depends on future decoding counts.

The variables next_one and next_two store the equivalent of dp[i+1] and dp[i+2]. This eliminates the need for an entire DP array and reduces space complexity to constant space.

When the current character is '0', the result is immediately 0 because zero cannot be decoded independently. Otherwise, we begin with the one-digit decoding count by assigning current = next_one.

The two-digit validation checks whether the current digit and the next digit form a number between 10 and 26. Instead of converting substrings into integers, the solution performs direct character comparisons, which is slightly more efficient.

After computing the current state, the rolling variables are updated so the next iteration has access to the correct future values.

Go Solution

func numDecodings(s string) int {
	n := len(s)

	nextOne := 1
	nextTwo := 0

	for i := n - 1; i >= 0; i-- {
		current := 0

		if s[i] != '0' {
			current = nextOne

			if i+1 < n &&
				(s[i] == '1' ||
					(s[i] == '2' && s[i+1] <= '6')) {
				current += nextTwo
			}
		}

		nextTwo = nextOne
		nextOne = current
	}

	return nextOne
}

The Go implementation follows the same logic as the Python version. Since strings in Go are byte slices, accessing characters with s[i] returns a byte, making character comparison straightforward.

No special handling for empty input is required because the constraints guarantee at least one character. Integer overflow is also not a concern because the problem guarantees the answer fits within a 32-bit integer.

Worked Examples

Example 1: s = "12"

We process from right to left.

Index	Character	One Digit Valid	Two Digits Valid	Current Ways	nextOne	nextTwo
Start	-	-	-	-	1	0
1	"2"	Yes	No	1	1	1
0	"1"	Yes	"12" valid	2	2	1

Final answer: 2

Valid decodings:

• "1", "2" → "AB"
• "12" → "L"

Example 2: s = "226"

Index	Character	One Digit Valid	Two Digits Valid	Current Ways	nextOne	nextTwo
Start	-	-	-	-	1	0
2	"6"	Yes	No	1	1	1
1	"2"	Yes	"26" valid	2	2	1
0	"2"	Yes	"22" valid	3	3	2

Final answer: 3

Valid decodings:

• "2", "2", "6" → "BBF"
• "22", "6" → "VF"
• "2", "26" → "BZ"

Example 3: s = "06"

Index	Character	One Digit Valid	Two Digits Valid	Current Ways	nextOne	nextTwo
Start	-	-	-	-	1	0
1	"6"	Yes	No	1	1	1
0	"0"	No	Invalid	0	0	1

Final answer: 0

The leading zero makes the string invalid.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only a constant number of variables are stored

The algorithm scans the string a single time from right to left, making the runtime linear in the input size. Since only three integer variables are maintained regardless of input length, the auxiliary space remains constant.

Test Cases

solution = Solution()

assert solution.numDecodings("12") == 2       # Basic two-way decoding
assert solution.numDecodings("226") == 3      # Multiple valid partitions
assert solution.numDecodings("06") == 0       # Leading zero is invalid

assert solution.numDecodings("1") == 1        # Single valid digit
assert solution.numDecodings("0") == 0        # Single zero invalid
assert solution.numDecodings("10") == 1       # Only "10" works
assert solution.numDecodings("20") == 1       # Only "20" works
assert solution.numDecodings("30") == 0       # Invalid pair

assert solution.numDecodings("27") == 1       # "27" cannot pair
assert solution.numDecodings("26") == 2       # "2,6" and "26"

assert solution.numDecodings("100") == 0      # Trailing zero invalidates
assert solution.numDecodings("101") == 1      # Valid internal zero
assert solution.numDecodings("110") == 1      # Must decode as "1,10"

assert solution.numDecodings("11106") == 2    # Example from prompt explanation
assert solution.numDecodings("111111") == 13  # Fibonacci-like growth

assert solution.numDecodings("2611055971756562") == 4  # Complex mixed case

Test	Why
"12"	Basic branching case
"226"	Multiple valid decoding paths
"06"	Leading zero invalidation
"1"	Smallest valid input
"0"	Smallest invalid input
"10"	Zero valid only in pair
"20"	Another valid zero pair
"30"	Invalid two-digit number
"27"	Pair exceeds 26
"26"	Largest valid pair
"100"	Invalid trailing zero
"101"	Internal zero handling
"110"	Forced valid grouping
"11106"	Mixed valid and invalid paths
"111111"	Many overlapping subproblems
"2611055971756562"	Stress case with mixed patterns

Edge Cases

Leading Zero

Inputs such as "06" or "012" are invalid because no letter corresponds to zero by itself. A naive implementation may accidentally interpret "06" as "6", which would be incorrect.

The implementation handles this naturally by assigning current = 0 whenever s[i] == '0'. This prevents invalid paths from contributing to the count.

Zeros in the Middle of the String

Cases like "10" and "101" are tricky because zero can only appear as part of "10" or "20".

For "101":

• "10" is valid
• "01" is invalid

The implementation correctly validates only legal two-digit combinations between 10 and 26, ensuring that zeros are counted only when paired appropriately.

Invalid Two-Digit Numbers

Strings such as "27" or "30" can be misleading.

• "26" is valid because it maps to 'Z'
• "27" is not a valid pair because 27 > 26
• "30" is invalid because zero cannot stand alone and "30" is not mapped

The implementation checks two-digit validity carefully using:

s[i] == '1' or (s[i] == '2' and s[i + 1] <= '6')

This guarantees only valid encodings contribute to the total count.

Very Long Inputs

A recursive brute-force solution would become extremely slow for inputs near length 100 because of exponential recomputation.

The dynamic programming implementation avoids this issue entirely by solving each position once, ensuring efficient execution even for the maximum allowed input size.