Decode Ways
Medium
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.
Example 1:
s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
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.
What are the time and space complexities of your solution?
Solution
Decoding a Digit String: Number of Ways
Problem
Given a string s containing only digits, determine the number of ways to decode it. The mapping is as follows:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
For instance, "12" can be decoded as "AB" (1, 2) or "L" (12). The string "226" can be decoded as "BZ" (2, 26), "VF" (22, 6), or "BBF" (2, 2, 6).
Brute Force (Recursive) Approach
A straightforward approach involves recursion. We can explore all possible groupings of digits (single or double digits) and check if they represent valid codes (1-26). If a grouping is valid, we proceed to decode the remaining part of the string.
Code (Python)
def num_decodings_recursive(s):
if not s:
return 1
if s[0] == '0':
return 0
count = 0
# Single digit
count += num_decodings_recursive(s[1:])
# Two digits
if len(s) >= 2 and 10 <= int(s[:2]) <= 26:
count += num_decodings_recursive(s[2:])
return count
Time Complexity
The time complexity is exponential, approximately O(2^n), where n is the length of the string, as we explore each possible branch of the recursion tree.
Space Complexity
The space complexity is O(n) due to the depth of the recursion stack.
Edge Cases
- Leading zeros: If the string starts with '0', there is no valid decoding.
- Invalid two-digit combinations: If a two-digit combination exceeds 26, it's invalid.
Optimal Solution: Dynamic Programming
A more efficient solution can be achieved using dynamic programming. We create a dp array where dp[i] represents the number of ways to decode the substring s[:i]. The base cases are dp[0] = 1 (empty string has one way to decode) and dp[1] = 1 if s[0] != '0'. Otherwise, dp[1] = 0.
Code (Python)
def num_decodings_dp(s):
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, n + 1):
# Single digit
if '1' <= s[i-1] <= '9':
dp[i] += dp[i-1]
# Two digits
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]
Time Complexity
The time complexity is O(n), where n is the length of the string, as we iterate through the string once to populate the dp array.
Space Complexity
The space complexity is O(n) to store the dp array. This can be further optimized to O(1) by storing only the previous two values, but for clarity, we'll stick to the O(n) space complexity.
Edge Cases
- Leading zeros: The initial handling of
dp[1]considers cases where the first digit is zero. - Invalid two-digit combinations: We check if the two-digit combination is within the valid range (10-26).
- Zero as a single digit: Check whether the digit is between 1 and 9.
