{x}
blog image

Decode Ways

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.

The test cases are generated so that the answer fits in a 32-bit integer.

 

Example 1:

Input: s = "12"

Output: 2

Explanation:

"12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"

Output: 3

Explanation:

"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"

Output: 0

Explanation:

"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

 

Constraints:

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

91. Decode Ways

Problem Description

Given a string s containing only digits, determine the number of ways to decode it. Each digit maps to a letter (1-A, 2-B, ..., 26-Z). A zero is invalid. Overlapping codes are possible (e.g., "12" can be "AB" or "L"). Return 0 if no valid decoding exists.

Solution: Dynamic Programming

This problem is elegantly solved using dynamic programming. We build an array dp where dp[i] represents the number of ways to decode the substring s[0...i-1].

Base Cases:

  • dp[0] = 1 (empty substring has one way to decode - the empty decoding)
  • dp[1] = 1 if s[0] is a valid digit (not '0'), otherwise 0.

Recursive Relation:

For i > 1, we consider two possibilities:

  1. Single Digit: If s[i-1] is not '0', we can decode it as a single digit, adding dp[i-1] ways to the count for dp[i].

  2. Two Digits: If s[i-2]s[i-1] forms a number between 10 and 26 (inclusive), we can decode it as a two-digit code, adding dp[i-2] ways to dp[i].

Therefore, the recursive relation is:

dp[i] = dp[i-1] + dp[i-2] (if both single and two-digit decodings are valid)

Optimization:

We can optimize space complexity to O(1) by noticing that dp[i] only depends on dp[i-1] and dp[i-2]. We can track these two values with variables instead of the entire array.

Code (Python)

With DP Array:

def numDecodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # Empty substring has one decoding
 
    if n > 0 and s[0] != '0':
        dp[1] = 1
 
    for i in range(2, n + 1):
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]
        if s[i - 2] == '1' or (s[i - 2] == '2' and s[i - 1] in '0123456'):
            dp[i] += dp[i - 2]
 
    return dp[n]

Optimized with Variables:

def numDecodings_optimized(s):
    prev2 = 1  # dp[i-2]
    prev1 = 1 if s and s[0] != '0' else 0 # dp[i-1]
 
    for i in range(2, len(s) + 1):
        curr = 0
        if s[i - 1] != '0':
            curr += prev1
        if s[i - 2] == '1' or (s[i - 2] == '2' and s[i - 1] in '0123456'):
            curr += prev2
        prev2 = prev1
        prev1 = curr
 
    return prev1

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
  • Space Complexity: O(n) for the DP array version, and O(1) for the optimized version.

Example Usage

print(numDecodings("12"))  # Output: 2
print(numDecodings("226")) # Output: 3
print(numDecodings("06"))  # Output: 0
print(numDecodings_optimized("12"))  # Output: 2
print(numDecodings_optimized("226")) # Output: 3
print(numDecodings_optimized("06"))  # Output: 0

The optimized version provides the same functionality with significantly improved space efficiency, making it preferable for larger input strings. Both versions correctly handle edge cases such as leading zeros and invalid two-digit codes.