Decode Ways

Medium

Google

5 views

Topics:

Dynamic Programming

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).

Decode Ways

Medium

Google

5 views

Topics:

Dynamic Programming

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).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` contain leading zeros, and how should they be handled?
Can the input string `s` be empty or null, and if so, what should I return?
Is the input guaranteed to only contain digits, or could there be other characters?
If a sequence of digits cannot be decoded (e.g., "06"), should I return 0 or throw an exception?
What is the maximum length of the input string `s`? Is it small enough to fit comfortably in memory for a DP approach?

Brute Force Solution

Approach

The brute force approach to decoding a message is like trying every single possible way to break it down. We check each potential decoding to see if it makes sense according to the rules.

Here's how the algorithm would work step-by-step:

Start at the beginning of the encoded message.
Try decoding the first single digit.
If that's a valid decoding, see how many ways you can decode the rest of the message after that first digit.
Now, go back to the start and try decoding the first two digits together as a single number.
If that's a valid decoding, see how many ways you can decode the rest of the message after those two digits.
Keep doing this, trying all possible combinations of single-digit and two-digit decodings from each point in the message.
Each time you reach the end of the message with a valid set of decodings, count it as one possible way.
In the end, add up all the possible ways you found to decode the whole message.

Code Implementation

def decode_ways_brute_force(encoded_message):
    def number_of_ways_to_decode(index):
        # If we reach the end of the string, it's one valid way
        if index == len(encoded_message):
            return 1

        # If we start with a zero, it's not a valid encoding
        if encoded_message[index] == '0':
            return 0

        number_of_ways = 0

        # Try decoding one digit
        number_of_ways += number_of_ways_to_decode(index + 1)

        # Try decoding two digits if possible
        if index + 1 < len(encoded_message):
            two_digit = int(encoded_message[index:index + 2])

            # Must be between 10 and 26 inclusive
            if 10 <= two_digit <= 26:
                number_of_ways += number_of_ways_to_decode(index + 2)

        return number_of_ways

    return number_of_ways_to_decode(0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores all possible combinations of single and double-digit decodings. For each digit in the input string of length n, we have potentially two choices: decode it as a single digit or as part of a two-digit number. This branching at each position leads to a binary tree-like exploration of possibilities. Therefore, in the worst case, the number of possible decodings grows exponentially with the length of the input string, resulting in a time complexity of O(2^n).

Space Complexity

O(N) – The brute force approach, as described, involves trying all possible combinations of single-digit and two-digit decodings using recursion. Each recursive call creates a new stack frame that stores the current position in the encoded message. In the worst-case scenario, where the input string 's' consists of all single-digit encodings (e.g., "11111"), the maximum depth of the recursion will be equal to the length of the string, N, where N is the length of the encoded message. Therefore, the auxiliary space used by the recursion stack is O(N).

Optimal Solution

Approach

The best way to solve this problem is to work backwards. Instead of figuring out how many ways to decode the entire message from the beginning, figure out how many ways to decode the last few characters and build up from there, reusing previous calculations.

Here's how the algorithm would work step-by-step:

Start at the very end of the message.
Think about how many ways you can decode the last single character. If it's a valid digit (1-9), there's one way. If it's zero, there are zero ways.
Now, think about the last two characters. If they form a valid number (10-26), that gives you an additional way to decode the ending.
Move one step to the left, considering the current character and the one after it. Reuse the results you already calculated for the ending parts of the message. If they form a valid encoding (1-9 for a single digit, or 10-26 for a two-digit combination), add the number of ways those parts can be decoded to your current total.
Keep working your way backwards, always reusing the already computed results, until you reach the beginning of the message.
The final answer is the number of ways you can decode the message starting from the very beginning.

Code Implementation

def decode_ways(encoded_message):
    message_length = len(encoded_message)
    
    # Initialize array to store number of ways to decode
    number_of_ways = [0] * (message_length + 1)
    number_of_ways[message_length] = 1

    # Iterate backwards through the encoded message
    for index in range(message_length - 1, -1, -1):
        # If the digit is '0', there are no ways to decode
        if encoded_message[index] == '0':
            number_of_ways[index] = 0
        else:
            # Add ways to decode from next index
            number_of_ways[index] = number_of_ways[index + 1]

        # Check if a two-digit combination is possible
        if index + 1 < message_length and (encoded_message[index] == '1' or (encoded_message[index] == '2' and int(encoded_message[index + 1]) <= 6)):
            # Add the number of ways from two indices ahead
            number_of_ways[index] += number_of_ways[index + 2]

    # The first value contains total possible ways
    return number_of_ways[0]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates backward through the input string of length n. At each position, it performs a constant amount of work: checking one or two digits and adding previously computed results from at most two subsequent positions. Since each position is visited and processed only once, the time complexity is directly proportional to the length of the input string. Thus, the runtime is O(n).

Space Complexity

O(N) – The solution uses dynamic programming, working backwards from the end of the string. It reuses previously calculated results to determine the number of decoding ways. This implies storing the number of ways to decode the message from each index to the end. Thus, an auxiliary data structure, specifically an array, of size N (where N is the length of the input string), is implicitly created to store these intermediate results. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return 1, as an empty string has one way to decode (no characters).
Input string starts with '0'	Return 0, as no letter maps to '0' directly, thus it cannot be the start of a valid decoding.
Input string contains '0' in the middle which is not preceded by '1' or '2'	Return 0, because '0' cannot be decoded alone and it's not part of a valid two-digit combination.
Input string contains '10' or '20'	These are valid two-digit encodings, so handle them appropriately when calculating the number of ways.
Input string contains '11' to '19' or '21' to '26'	These are valid two-digit encodings, so handle them appropriately when calculating the number of ways.
Input string with only '0's after a valid starting sequence (e.g. 100, 200)	Return 0, as after the initial 10 or 20, the subsequent 0s cannot be decoded.
Very long input string	Use dynamic programming to avoid redundant calculations and potential stack overflow issues from recursion, ensuring efficient scaling.
Input string contains two-digit sequence greater than 26.	Treat the two digits as separate single-digit encodings in this case.