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

Number: 91

Difficulty: Medium

Paid? No

Companies: Google, Goldman Sachs, Meta, Amazon, Lyft, Microsoft, TikTok, Zoho, Apple, Moengage, Commvault, Bloomberg, Salesforce, Uber, Snap, Oracle, Flipkart, Walmart Labs, Intuit

Problem Description

Given a string s containing only digits, count the number of ways to decode it into letters using the mapping: "1" -> 'A', "2" -> 'B', ..., "26" -> 'Z'. If the string cannot be fully decoded, return 0.

Key Insights

  • A digit '0' cannot be mapped on its own; it must be part of "10" or "20".
  • Use dynamic programming where dp[i] represents the number of ways to decode the substring s[0...i-1].
  • For each index i, if the digit at position i-1 is non-zero, add dp[i-1] to dp[i].
  • If the two-digit number formed by s[i-2] and s[i-1] is between 10 and 26, add dp[i-2] to dp[i].
  • Initialize dp[0] as 1 (an empty string has one way to be decoded).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n), due to the dp array (which can be optimized to O(1)).

Solution

We solve the problem using a dynamic programming approach. We initialize a dp array where dp[i] indicates the number of ways to decode the substring s[0...i-1]. We set dp[0] = 1 since an empty string is trivially decodable. We loop through the string, and at each step:

  • If s[i-1] is not '0', we add dp[i-1] to dp[i] because s[i-1] can be mapped to a valid letter.
  • If the substring s[i-2:i] (for i >= 2) forms a valid two-digit number between 10 and 26, we add dp[i-2] to dp[i]. This cumulative approach yields the total ways to decode the string, and if the string starts with '0' or contains invalid sequences, dp[n] will eventually be 0.

Code Solutions

# Python solution using dynamic programming
def num_decodings(s: str) -> int:
    # If the string starts with '0', it's not decodable
    if not s or s[0] == '0':
        return 0

    # dp array where dp[i] represents the number of ways to decode s[:i]
    n = len(s)
    dp = [0] * (n + 1)
    
    # Base case: an empty string has one decoding
    dp[0] = 1
    
    for i in range(1, n + 1):
        # Check for single digit decoding (s[i-1] is valid if not '0')
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]
        # Check for two-digit decoding (if i>=2, s[i-2:i] forms a valid number between 10 and 26)
        if i >= 2 and s[i - 2] != '0':  
            two_digit = int(s[i - 2:i])
            if 10 <= two_digit <= 26:
                dp[i] += dp[i - 2]
    return dp[n]

# Example usage:
print(num_decodings("12"))  # Expected output: 2
← Back to All Questions