Decode Ways

LeetCode 91: Decode Ways Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a 1D Dynamic Programming approach similar to the Fibonacci sequence, where the number of ways to decode at index i is the sum of valid decoding paths from the previous single digit and the previous two digits.

The "Decode Ways" problem asks us to determine how many distinct ways a string of digits can be translated into alphabetic characters. The mapping is standard: '1' becomes 'A', '2' becomes 'B', up to '26' becoming 'Z'. The complexity in LeetCode 91 arises from ambiguity; a sequence like "12" can be interpreted as "AB" (1, 2) or "L" (12). Furthermore, the input may contain zeros, which are only valid when combined with a preceding '1' or '2' (e.g., "10" or "20").

Brute Force Approach for Decode Ways

A naive approach to solving LeetCode 91 involves recursion. We can iterate through the string and, at each step, attempt to decode either one digit or two digits.

If we take one digit, we recursively solve for the remainder of the string. If we take two digits (provided they form a valid number between 10 and 26), we also recursively solve for the remainder.

Pseudo-code:

function countWays(index, s):
    if index == length(s): return 1 // Found a valid path
    if s[index] == '0': return 0 // Invalid path

    ways = countWays(index + 1, s) // Take 1 digit
    
    if (index + 1 < length(s)) and (s[index...index+1] is valid):
        ways += countWays(index + 2, s) // Take 2 digits
        
    return ways

Why this fails: The time complexity of this approach is $O(2^N)$, where $N$ is the length of the string. This is because every decision point branches into two potential recursive calls. For a string of length 100 (as allowed by the constraints), the recursion tree grows exponentially, leading to a Time Limit Exceeded (TLE) error. This approach blindly recalculates the number of ways to decode the same suffixes repeatedly (overlapping subproblems).

Algorithm Strategy: DP - 1D Array

We will implement this using a 1D array (or table) to store our intermediate results.

1. State Definition: Initialize an array dp of size n + 1, where n is the length of string s. dp[i] corresponds to the number of ways to decode the prefix s[0...i-1].
2. Base Cases:
   • dp[0] = 1: An empty string has one theoretical way to be decoded (doing nothing). This is necessary for the math to work when decoding the first two characters.
   • dp[1]: If s[0] == '0', dp[1] = 0 (and effectively the whole result is 0). Otherwise dp[1] = 1.
3. Iteration: Loop from i = 2 to n.
   • One-digit check: Extract the digit at s[i-1]. If it is between '1' and '9', add dp[i-1] to dp[i].
   • Two-digit check: Extract the substring s[i-2]s[i-1]. If it forms a value between 10 and 26, add dp[i-2] to dp[i].
4. Result: The final answer is stored in dp[n].

This strategy enforces the constraints naturally. Leading zeros result in 0 additions. Invalid pairs (like "99") result in 0 additions from the i-2 state.

Execution Flow

Let's trace the algorithm with s = "226".

1. Initialization:

   • n = 3.
   • Create dp array of size 4: [0, 0, 0, 0].
   • dp[0] = 1.

2. Base Case (Index 1):

   • s[0] is '2' (not '0').
   • dp[1] = 1.
   • Array: [1, 1, 0, 0].

3. Iteration i = 2 (Current char '2', Prefix "22"):

   • 1-digit check: s[1] is '2'. Valid. dp[2] += dp[1] (which is 1).
   • 2-digit check: s[0...1] is "22". Valid (10 <= 22 <= 26). dp[2] += dp[0] (which is 1).
   • dp[2] = 1 + 1 = 2.
   • Array: [1, 1, 2, 0].

4. Iteration i = 3 (Current char '6', Prefix "226"):

   • 1-digit check: s[2] is '6'. Valid. dp[3] += dp[2] (which is 2).
   • 2-digit check: s[1...2] is "26". Valid (10 <= 26 <= 26). dp[3] += dp[1] (which is 1).
   • dp[3] = 2 + 1 = 3.
   • Array: [1, 1, 2, 3].

5. Termination:

   • Return dp[3], which is 3.

Proof of Correctness

The correctness relies on the exhaustive nature of the recurrence relation. For any valid decoding of a string ending at i, the last component must be either a single digit (A-I) or a double digit (J-Z).

• If the last component is a single digit, the number of ways is exactly the number of ways to decode the prefix ending at i-1.
• If the last component is a double digit, the number of ways is exactly the number of ways to decode the prefix ending at i-2.
• Since these two cases are mutually exclusive at the final step (you cannot end with both a 1-digit code and a 2-digit code simultaneously), the sum of these possibilities covers the entire sample space of valid decodings.

Pattern Reuse Notes

The DP - 1D Array (Fibonacci Style) pattern is fundamental. Understanding LeetCode 91 helps solve several other popular interview questions:

• LeetCode 70: Climbing Stairs - This is the simplified version of Decode Ways. There are no validity checks (1 step or 2 steps are always valid), so it is exactly the Fibonacci sequence.
• LeetCode 198: House Robber - Uses the same i-1 vs i-2 logic, but instead of summing the counts, we maximize the value (money robbed).
• LeetCode 213: House Robber II - Applies the House Robber logic on a circular array.
• LeetCode 337: House Robber III - Applies similar inclusion/exclusion logic but on a binary tree structure.

Reference Implementation

C++ Solution for LeetCode 91

1class Solution {
2public:
3    int numDecodings(string s) {
4        if (s.empty() || s[0] == '0') {
5            return 0;
6        }
7
8        int n = s.length();
9        // dp[i] represents number of ways to decode string of length i
10        vector<int> dp(n + 1, 0);
11
12        dp[0] = 1; // Base case for empty string logic
13        dp[1] = 1; // We already checked s[0] != '0'
14
15        for (int i = 2; i <= n; ++i) {
16            // Check if single digit is valid (1-9)
17            int oneDigit = s[i - 1] - '0';
18            if (oneDigit >= 1 && oneDigit <= 9) {
19                dp[i] += dp[i - 1];
20            }
21
22            // Check if two digits are valid (10-26)
23            int twoDigits = stoi(s.substr(i - 2, 2));
24            if (twoDigits >= 10 && twoDigits <= 26) {
25                dp[i] += dp[i - 2];
26            }
27        }
28
29        return dp[n];
30    }
31};

Java Solution for LeetCode 91

1class Solution {
2    public int numDecodings(String s) {
3        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
4            return 0;
5        }
6
7        int n = s.length();
8        int[] dp = new int[n + 1];
9
10        // Base cases
11        dp[0] = 1; 
12        dp[1] = 1;
13
14        for (int i = 2; i <= n; i++) {
15            // Check single digit (current char)
16            int oneDigit = s.charAt(i - 1) - '0';
17            if (oneDigit >= 1 && oneDigit <= 9) {
18                dp[i] += dp[i - 1];
19            }
20
21            // Check two digits (prev char + current char)
22            int twoDigits = Integer.parseInt(s.substring(i - 2, i));
23            if (twoDigits >= 10 && twoDigits <= 26) {
24                dp[i] += dp[i - 2];
25            }
26        }
27
28        return dp[n];
29    }
30}

Python Solution for LeetCode 91

1class Solution:
2    def numDecodings(self, s: str) -> int:
3        if not s or s[0] == '0':
4            return 0
5            
6        n = len(s)
7        # dp[i] = ways to decode string of length i
8        dp = [0] * (n + 1)
9        
10        dp[0] = 1
11        dp[1] = 1
12        
13        for i in range(2, n + 1):
14            # Check single digit
15            one_digit = int(s[i-1])
16            if 1 <= one_digit <= 9:
17                dp[i] += dp[i-1]
18                
19            # Check two digits
20            two_digits = int(s[i-2:i])
21            if 10 <= two_digits <= 26:
22                dp[i] += dp[i-2]
23                
24        return dp[n]