We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Decode Ways II

Difficulty: Hard

Problem Description

A message containing letters from A-Z can be encoded into numbers using a specific mapping, where 'A' maps to "1", 'B' to "2", and so on up to 'Z' which maps to "26". Additionally, the encoded message may contain the '' character, which can represent any digit from '1' to '9'. The task is to determine the number of ways to decode the encoded message represented as a string containing digits and '' characters.

Key Insights

  • Each digit from '1' to '9' has a unique mapping to letters.
  • Digits '10' and '26' can represent two-letter combinations.
  • The '*' character can represent any digit from '1' to '9', leading to multiple decoding possibilities.
  • Dynamic Programming is a suitable approach to keep track of the number of ways to decode substrings of the input.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), as we only need to store a few variables for calculations.

Solution

The solution employs a dynamic programming approach. We initialize two variables to keep track of the number of ways to decode the current and previous characters. As we iterate through the string, we update these counts based on the current character and the previous character.

  1. If the current character is '*', it has 9 potential mappings (1-9).
  2. If the previous character is '1', the current character can be decoded as '1X' or '2X' if it's '2'.
  3. We ensure to handle combinations correctly, especially when the previous character is '*', which can also provide multiple decoding options.

The final result is computed modulo 10^9 + 7 to handle large numbers.

Code Solutions

def numDecodings(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    
    if n == 0:
        return 0
    
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 9 if s[0] == '*' else 1 if s[0] != '0' else 0
    
    for i in range(2, n + 1):
        current = s[i - 1]
        previous = s[i - 2]
        
        if current == '*':
            dp[i] = (dp[i - 1] * 9) % MOD
        else:
            dp[i] = dp[i - 1] if current != '0' else 0
        
        if previous == '1':
            dp[i] = (dp[i] + dp[i - 2]) % MOD
        elif previous == '2':
            dp[i] = (dp[i] + dp[i - 2] * (1 if current <= '6' else 0)) % MOD
        elif previous == '*':
            dp[i] = (dp[i] + dp[i - 2] * (9 if current <= '9' else 0)) % MOD
    
    return dp[n]
← Back to All Questions