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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Decode Ways II

Number: 639

Difficulty: Hard

Paid? No

Companies: PhonePe, Meta

Problem Description

Given a string s that consists of digits and the '*' wildcard character (which represents any digit from '1' to '9'), determine the number of ways to decode it. Each digit or pair of digits (with valid mapping 'A' = 1 to 'Z' = 26) can be mapped back to a letter. The answer should be computed modulo 10^9 + 7.

Key Insights

  • Use dynamic programming where dp[i] represents the number of ways to decode the substring up to index i.
  • Process one-character and two-character decoding possibilities separately.
  • Carefully handle '*' characters; they can represent 9 possibilities on their own, but when forming two-digit numbers, combinations vary based on the digit they pair with.
  • Optimize space by only keeping track of the last two dp state values.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), using constant space by tracking only the last two dp values.

Solution

The solution is based on dynamic programming. We iterate over the string while maintaining two variables (dp0 and dp1) that represent the number of decoding ways for the substring ending at the previous two positions. For each character, we process:

  1. Single-digit decoding: If the current character is '*' it contributes 9 ways; if it is a non-'0' digit, it contributes 1 way.
  2. Two-digit decoding: The number of ways depends on the previous character and current character, and special handling is required when either or both are ''. For instance, if the previous character is '' and current is '', there are 15 valid combinations (from treating '' as '1' or '2'). Finally, we update our dp state while applying modulo arithmetic.

Code Solutions

# Python solution for Decode Ways II
MOD = 10**9 + 7

def numDecodings(s: str) -> int:
    # dp0: ways ending at index i-2, dp1: ways ending at index i-1
    dp0, dp1 = 1, 0
    # Initialize for the first character
    if s[0] == '*':
        dp1 = 9
    elif s[0] != '0':
        dp1 = 1
    else:
        dp1 = 0

    for i in range(1, len(s)):
        dp2 = 0
        current = s[i]
        prev = s[i - 1]
        
        # Single digit decoding for current character
        if current == '*':
            dp2 += dp1 * 9
        elif current != '0':
            dp2 += dp1
        
        # Two digit decoding using previous character and current character
        if prev == '1':
            if current == '*':
                dp2 += dp0 * 9  # valid pairs 11-19
            else:
                dp2 += dp0      # valid pair 10-19
        elif prev == '2':
            if current == '*':
                dp2 += dp0 * 6  # valid pairs 21-26
            elif '0' <= current <= '6':
                dp2 += dp0
        elif prev == '*':
            if current == '*':
                dp2 += dp0 * 15  # '*' can be 1 or 2: 11-19 (9 ways) and 21-26 (6 ways)
            else:
                if '0' <= current <= '6':
                    dp2 += dp0 * 2  # either 1 or 2 can lead to a valid pair
                else:
                    dp2 += dp0      # only '1' works to form a valid pair
        
        dp2 %= MOD
        dp0, dp1 = dp1, dp2

    return dp1

# Sample test cases
print(numDecodings("*"))    # Expected output: 9
print(numDecodings("1*"))   # Expected output: 18
print(numDecodings("2*"))   # Expected output: 15
← Back to All Questions