LeetCode 639 - Decode Ways II

The problem asks us to determine the number of ways an encoded string can be decoded into letters, where 'A' maps to "1", 'B' maps to "2", up to 'Z' mapping to "26".

leetcodehardstringdynamic-programming

LeetCode Problem 639

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to determine the number of ways an encoded string can be decoded into letters, where 'A' maps to "1", 'B' maps to "2", up to 'Z' mapping to "26". The input string s contains digits '0'-'9' and potentially the wildcard character '*', which represents any digit from '1' to '9'. The output is the total number of valid decodings modulo $10^9 + 7$.

The key challenges are handling the '*' wildcard and ensuring that combinations of one-digit and two-digit numbers are correctly counted without double counting or including invalid sequences like "06". The string can be up to $10^5$ characters long, which rules out brute-force recursion due to exponential growth in the number of combinations.

Important edge cases include strings consisting entirely of '*', sequences containing '0' (which can only be part of '10' or '20'), and strings that mix digits and '*' in a way that creates multiple valid interpretations.

Approaches

The brute-force approach is to recursively consider every character in the string as either a single-digit decoding or, if possible, a two-digit decoding. For '*', we would iterate through all 9 possible digits at that position. This is correct in theory but infeasible due to exponential time complexity, $O(9^n)$, where $n$ is the length of the string.

The optimal approach uses dynamic programming. Let dp[i] represent the number of ways to decode the substring s[0:i]. The transition considers one-character and two-character combinations. For one-character, if s[i-1] is '*', it contributes 9 times dp[i-1]; otherwise, it contributes 1 if not '0'. For two-character combinations, we consider the valid ranges that form numbers from 10 to 26, carefully counting the possibilities when '*' appears in either position. The space can be optimized to O(1) by storing only the last two DP values, since each dp[i] only depends on dp[i-1] and dp[i-2].

Approach Time Complexity Space Complexity Notes
Brute Force O(9^n) O(n) Recursively explore all interpretations of * and digits
Optimal DP O(n) O(1) Use DP with modulo arithmetic and handle * carefully

Algorithm Walkthrough

  1. Initialize MOD = 10^9 + 7 to handle large numbers.

  2. Create two variables, dp1 and dp2, representing dp[i-1] and dp[i-2]. Initially, dp2 = 1 (empty string has 1 decoding), and dp1 depends on the first character: 9 if it is '*', 1 if non-zero digit, 0 if '0'.

  3. Iterate over the string from index 1 to n-1:

  4. Compute single for decoding s[i] as a single character: 9 if '*', 1 if digit '1'-'9', 0 if '0'.

  5. Compute double for decoding s[i-1] and s[i] as a two-digit number. Handle all combinations with '*' carefully:

  • If s[i-1] is '*' and s[i] is '*', valid two-digit numbers are 11-19 and 21-26 → total 15 combinations.
  • If only one is '*', count valid options based on the other digit.
  • If both are digits, check if they form a number between 10 and 26.
  1. Calculate dp = (dp1 * single + dp2 * double) % MOD.
  2. Update dp2 = dp1, dp1 = dp for the next iteration.
  3. Return dp1 as the total number of ways to decode the string.

Why it works: This DP correctly counts all combinations of single- and double-digit decodings, handling '*' efficiently. The modulo ensures we do not overflow. By storing only the last two DP values, we reduce space complexity without losing correctness, because each dp[i] only depends on dp[i-1] and dp[i-2].

Python Solution

class Solution:
    def numDecodings(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)
        if not s:
            return 0
        
        dp2 = 1
        dp1 = 9 if s[0] == '*' else 0 if s[0] == '0' else 1
        
        for i in range(1, n):
            single = 0
            double = 0
            
            if s[i] == '*':
                single = 9
            elif s[i] != '0':
                single = 1
            
            if s[i-1] == '*' and s[i] == '*':
                double = 15  # 11-19 + 21-26
            elif s[i-1] == '*':
                double = 2 if '0' <= s[i] <= '6' else 1
            elif s[i] == '*':
                if s[i-1] == '1':
                    double = 9
                elif s[i-1] == '2':
                    double = 6
            else:
                if s[i-1] != '0' and 10 <= int(s[i-1:i+1]) <= 26:
                    double = 1
            
            dp = (dp1 * single + dp2 * double) % MOD
            dp2, dp1 = dp1, dp
        
        return dp1

The code initializes base cases for dp[0] and dp[1] and iterates through the string, calculating the number of ways for single- and double-character decodings. It handles '*' by explicitly counting all possible digit values that form valid letters.

Go Solution

func numDecodings(s string) int {
    const MOD = 1_000_000_007
    n := len(s)
    if n == 0 {
        return 0
    }
    
    dp2, dp1 := 1, 0
    if s[0] == '*' {
        dp1 = 9
    } else if s[0] != '0' {
        dp1 = 1
    }
    
    for i := 1; i < n; i++ {
        single, double := 0, 0
        
        if s[i] == '*' {
            single = 9
        } else if s[i] != '0' {
            single = 1
        }
        
        if s[i-1] == '*' && s[i] == '*' {
            double = 15
        } else if s[i-1] == '*' {
            if s[i] >= '0' && s[i] <= '6' {
                double = 2
            } else {
                double = 1
            }
        } else if s[i] == '*' {
            if s[i-1] == '1' {
                double = 9
            } else if s[i-1] == '2' {
                double = 6
            }
        } else {
            if s[i-1] != '0' {
                twoDigit := (int(s[i-1]-'0')*10 + int(s[i]-'0'))
                if twoDigit >= 10 && twoDigit <= 26 {
                    double = 1
                }
            }
        }
        
        dp := (dp1*single + dp2*double) % MOD
        dp2, dp1 = dp1, dp
    }
    
    return dp1
}

The Go solution mirrors the Python implementation, with differences in syntax for integer conversion and modulo arithmetic. We use explicit casting to compute two-digit numbers and maintain only the last two DP values to reduce memory usage.

Worked Examples

Example: s = "1*"

i s[i] single double dp
0 '1' 1 - 1
1 '*' 9 9 18

Example: s = "2*"

i s[i] single double dp
0 '2' 1 - 1
1 '*' 9 6 15

Example: s = "*"

i s[i] single double dp
0 '*' 9 - 9

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through string with constant-time calculations per character
Space O(1) Only two DP values are maintained at any time

The algorithm scales linearly with