Decode Ways

Medium

Apple

1 view

Topics:

Dynamic ProgrammingStrings

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.

Examples:

Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Input: s = "226" Output: 3 Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
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.

How would you approach this problem efficiently?

Decode Ways

Medium

Apple

1 view

Topics:

Dynamic ProgrammingStrings

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.

Examples:

Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Input: s = "226" Output: 3 Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
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.

How would you approach this problem efficiently?

Solution

Let's explore how to solve the decoding problem efficiently.

Naive Approach (Brute Force with Recursion)

A straightforward way to approach this is by using recursion. We try all possible combinations of single and double-digit groupings.

Start from the beginning of the string.
For each position, try decoding one digit and then two digits (if possible).
Recursively call the function for the remaining string.
Sum up the number of ways each recursive call can decode the string.

Code (Python):

def num_decodings_recursive(s):
    def decode(index):
        if index == len(s):
            return 1
        
        if s[index] == '0':
            return 0
        
        if index == len(s) - 1:
            return 1
        
        ways = decode(index + 1)
        if 10 <= int(s[index:index+2]) <= 26:
            ways += decode(index + 2)
            
        return ways
    
    return decode(0)

Time Complexity: O(2ⁿ), where n is the length of the string, as each digit branches into (at most) two possibilities.

Space Complexity: O(n) due to the recursion depth.

Optimal Approach (Dynamic Programming)

We can optimize the solution using dynamic programming to avoid redundant calculations.

Create a DP array dp where dp[i] stores the number of ways to decode the substring s[i:].
Initialize dp[n] = 1 because an empty string has one way to decode (base case).
Iterate backwards from n-1 to 0.
If s[i] == '0', dp[i] = 0.
Otherwise, dp[i] = dp[i+1] (single digit).
If s[i:i+2] forms a valid two-digit number (10-26), add dp[i+2] to dp[i].

Code (Python):

def num_decodings_dp(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[n] = 1
    
    for i in range(n - 1, -1, -1):
        if s[i] == '0':
            dp[i] = 0
        else:
            dp[i] = dp[i+1]
            if i < n - 1 and 10 <= int(s[i:i+2]) <= 26:
                dp[i] += dp[i+2]
                
    return dp[0]

Time Complexity: O(n), where n is the length of the string, as we iterate through the string once.

Space Complexity: O(n) for the DP array. This can be further optimized to O(1) by storing only the last two values.

Optimized Space (O(1)):

def num_decodings_dp_optimized(s):
    n = len(s)
    dp1, dp2 = 1, 0
    
    for i in range(n - 1, -1, -1):
        current = 0
        if s[i] != '0':
            current = dp1
            if i < n - 1 and 10 <= int(s[i:i+2]) <= 26:
                current += dp2
        dp2 = dp1
        dp1 = current
    
    return dp1

Time Complexity: O(n)

Space Complexity: O(1)

Edge Cases:

Leading Zero: If the string starts with '0', there are no valid decodings.
"06" : Invalid because it should be treated as just 6 and not 06.
Empty String: An empty string has one way of being decoded (base case for DP).
Single '0': If any digit is '0' without a preceding '1' or '2', there are no valid decodings from that point onwards.

Solution

Let's explore how to solve the decoding problem efficiently.

Naive Approach (Brute Force with Recursion)

A straightforward way to approach this is by using recursion. We try all possible combinations of single and double-digit groupings.

Start from the beginning of the string.
For each position, try decoding one digit and then two digits (if possible).
Recursively call the function for the remaining string.
Sum up the number of ways each recursive call can decode the string.

Code (Python):

def num_decodings_recursive(s):
    def decode(index):
        if index == len(s):
            return 1
        
        if s[index] == '0':
            return 0
        
        if index == len(s) - 1:
            return 1
        
        ways = decode(index + 1)
        if 10 <= int(s[index:index+2]) <= 26:
            ways += decode(index + 2)
            
        return ways
    
    return decode(0)

Time Complexity: O(2ⁿ), where n is the length of the string, as each digit branches into (at most) two possibilities.

Space Complexity: O(n) due to the recursion depth.

Optimal Approach (Dynamic Programming)

We can optimize the solution using dynamic programming to avoid redundant calculations.

Create a DP array dp where dp[i] stores the number of ways to decode the substring s[i:].
Initialize dp[n] = 1 because an empty string has one way to decode (base case).
Iterate backwards from n-1 to 0.
If s[i] == '0', dp[i] = 0.
Otherwise, dp[i] = dp[i+1] (single digit).
If s[i:i+2] forms a valid two-digit number (10-26), add dp[i+2] to dp[i].

Code (Python):

def num_decodings_dp(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[n] = 1
    
    for i in range(n - 1, -1, -1):
        if s[i] == '0':
            dp[i] = 0
        else:
            dp[i] = dp[i+1]
            if i < n - 1 and 10 <= int(s[i:i+2]) <= 26:
                dp[i] += dp[i+2]
                
    return dp[0]

Time Complexity: O(n), where n is the length of the string, as we iterate through the string once.

Space Complexity: O(n) for the DP array. This can be further optimized to O(1) by storing only the last two values.

Optimized Space (O(1)):

def num_decodings_dp_optimized(s):
    n = len(s)
    dp1, dp2 = 1, 0
    
    for i in range(n - 1, -1, -1):
        current = 0
        if s[i] != '0':
            current = dp1
            if i < n - 1 and 10 <= int(s[i:i+2]) <= 26:
                current += dp2
        dp2 = dp1
        dp1 = current
    
    return dp1

Time Complexity: O(n)

Space Complexity: O(1)

Edge Cases:

Leading Zero: If the string starts with '0', there are no valid decodings.
"06" : Invalid because it should be treated as just 6 and not 06.
Empty String: An empty string has one way of being decoded (base case for DP).
Single '0': If any digit is '0' without a preceding '1' or '2', there are no valid decodings from that point onwards.