LeetCode Problem 91: Decode Ways

The Decode Ways problem (LeetCode #91) challenges us to determine the number of ways an encoded message, represented as a string of digits, can be decoded into letters using the mapping:

• ‘A’ → “1”
• ‘B’ → “2”
• …
• ‘Z’ → “26”

For example, the input "226" can be decoded as:

1. “BZ” (2 26)
2. “VF” (22 6)
3. “BBF” (2 2 6)

Resulting in 3 possible decodings.

Solution Approach

To solve this problem efficiently, we can employ a dynamic programming (DP) approach. The key insight is that the number of ways to decode a string up to the i-th character depends on the previous one or two characters.

Algorithm Steps

1. Initial Checks:
   • If the string is empty or starts with ‘0’, return 0 immediately since decoding is impossible.
2. DP Array Setup:
   • Create a DP array dp where dp[i] represents the number of ways to decode the substring s[0:i].
   • Initialize dp[0] = 1 to represent the base case of an empty string.
   • Set dp[1] = 1 if the first character is not ‘0’; otherwise, set it to 0.
3. Iterate Through the String (from the second character to the end):
   • Single Digit Check:
     • If the current character is between ‘1’ and ‘9’, add dp[i-1] to dp[i].
   • Two-Digit Check:
     • If the two-character substring s[i-2:i] forms a valid number between ’10’ and ’26’, add dp[i-2] to dp[i].

Complexity Analysis

• Time Complexity: O(n), where n is the length of the string. Each character is processed once.
• Space Complexity: O(n) for the DP array. This can be optimized to O(1) by using two variables to store the previous two values instead of maintaining the entire array.

Code Implementations

Here are the implementations of the above approach in various programming languages:

Java

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }

        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            int oneDigit = s.charAt(i - 1) - '0';
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));

            if (oneDigit >= 1) {
                dp[i] += dp[i - 1];
            }

            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
}

C++

#include <vector>
#include <string>

using namespace std;

int numDecodings(string s) {
    if (s.empty() || s[0] == '0') return 0;
    int n = s.size();
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    
    for (int i = 2; i <= n; ++i) {
        int oneDigit = s[i-1] - '0';
        int twoDigits = stoi(s.substr(i-2, 2));
        
        if (oneDigit >= 1) dp[i] += dp[i-1];
        if (twoDigits >= 10 && twoDigits <= 26) dp[i] += dp[i-2];
    }
    return dp[n];
}

Python

def numDecodings(s: str) -> int:
    if not s or s[0] == '0':
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        one_digit = int(s[i-1])
        two_digits = int(s[i-2:i])
        if one_digit >= 1:
            dp[i] += dp[i-1]
        if 10 <= two_digits <= 26:
            dp[i] += dp[i-2]
    return dp[n]

C#

public class Solution {
    public int NumDecodings(string s) {
        if (string.IsNullOrEmpty(s) || s[0] == '0') return 0;
        int n = s.Length;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int oneDigit = s[i-1] - '0';
            int twoDigits = int.Parse(s.Substring(i-2, 2));
            if (oneDigit >= 1) {
                dp[i] += dp[i-1];
            }
            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }
}

Edge Cases and Examples

1. Leading Zero: s = "0" → returns 0.
2. Valid Two-Digit: s = "10" → returns 1 (“10” as ‘J’).
3. Invalid Two-Digit: s = "27" → returns 1 (only ‘2’ and ‘7’).

Conclusion

The Decode Ways problem is a classic example of dynamic programming, where each decision depends on previous subproblems. By breaking down the problem into checking single and two-digit possibilities, we efficiently compute the total number of decoding ways. This approach ensures we handle all edge cases, including invalid zeros and out-of-range two-digit numbers. The provided solutions in C++, Java, Python, and C# demonstrate a clear and efficient way to solve this problem using DP.