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

Difficulty: Medium

Problem Description

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

  • "AAJF" with the grouping (1, 1, 10, 6)
  • "KJF" with the grouping (11, 10, 6)
  • The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode. Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

Key Insights

  • Each digit can represent a letter (1-26).
  • A "0" cannot stand alone and must be part of a valid two-digit number (10-26).
  • Use dynamic programming to store the number of ways to decode substrings of the input string.
  • The solution builds on previous counts depending on the current and previous characters.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), as we can optimize to use only two variables for tracking counts.

Solution

The problem can be solved using a dynamic programming approach. We will iterate through the string and maintain a count of the number of ways to decode up to the current character. We keep track of two previous counts: one for the last character and one for the character before that.

  1. Initialize two variables to represent the number of ways to decode up to the last and second-to-last characters.
  2. Loop through the string:
    • If the current character is not '0', it can be decoded as a single character, so we add the count from the previous character.
    • If the last two characters form a valid number (10-26), we add the count from two characters back.
  3. Return the count after processing the entire string.

Code Solutions

def numDecodings(s: str) -> int:
    if not s or s[0] == '0':
        return 0
    
    # Initialize previous counts
    prev2, prev1 = 1, 1
    
    for i in range(1, len(s)):
        current = 0
        
        # Check single digit decoding
        if s[i] != '0':
            current += prev1
        
        # Check double digit decoding
        if s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'):
            current += prev2
        
        # Update previous counts
        prev2, prev1 = prev1, current
    
    return prev1
← Back to All Questions