Decode Ways II

Hard

Asked by:

26 views

Topics:

Dynamic Programming

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

In addition to the mapping above, an encoded message may contain the '*' character, which can represent any digit from '1' to '9' ('0' is excluded). For example, the encoded message "1*" may represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19". Decoding "1*" is equivalent to decoding any of the encoded messages it can represent.

Given a string s consisting of digits and '*' characters, return the number of ways to decode it.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "*"
Output: 9
Explanation: The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9".
Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively.
Hence, there are a total of 9 ways to decode "*".

Example 2:

Input: s = "1*"
Output: 18
Explanation: The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19".
Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K").
Hence, there are a total of 9 * 2 = 18 ways to decode "1*".

Example 3:

Input: s = "2*"
Output: 15
Explanation: The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29".
"21", "22", "23", "24", "25", and "26" have 2 ways of being decoded, but "27", "28", and "29" only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode "2*".

Constraints:

1 <= s.length <= 10⁵
s[i] is a digit or '*'.

Try coding it in LeetCode

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:

The input string can contain '*' which can represent any digit from 1-9. What should I do if a '0' is encountered?
What is the maximum length of the input string? Should I be concerned about integer overflow when calculating the number of ways?
If the input string cannot be decoded at all, what value should I return?
Are there any leading zeros in the input string that should be considered invalid (e.g., '06')?
Can I assume that the input string only contains digits and asterisks, or do I need to handle other characters?

Brute Force Solution

Approach

We're trying to find how many ways we can decode a secret message. The brute force way is to try every single possible decoding, one by one, until we've looked at absolutely everything.

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

Start by trying to decode just the very first part of the message.
See how many ways that first part can be decoded.
For each of those ways, try decoding the next part of the message.
Continue this process, exploring all possible combinations of decodings for each part.
If you hit a dead end (a part that can't be decoded), just go back and try a different path.
Keep a count of every valid decoding you find.
Once you've explored every single possible combination, the final count is your answer.

Code Implementation

def decode_ways_brute_force(encoded_string):
    number_of_ways = 0

    def recursive_decode(current_index, current_decoding):
        nonlocal number_of_ways

        # Base case: If we've reached the end, it's a valid decoding
        if current_index == len(encoded_string):
            number_of_ways += 1
            return

        # Try decoding one character
        first_character = encoded_string[current_index]
        
        if first_character == '*':
            # '*' can be 1-9
            for i in range(1, 10):
                recursive_decode(current_index + 1, current_decoding + str(i))
        elif first_character != '0':
            recursive_decode(current_index + 1, current_decoding + first_character)

        # Try decoding two characters, if possible
        if current_index < len(encoded_string) - 1:
            first_character = encoded_string[current_index]
            second_character = encoded_string[current_index + 1]

            #Handle all the * cases for 2 digits
            if first_character == '*' and second_character == '*':
                # Since ** can represent 11-19 and 21-26
                for i in range(11, 20):
                    recursive_decode(current_index + 2, current_decoding + str(i))
                for i in range(21, 27):
                    recursive_decode(current_index + 2, current_decoding + str(i))

            elif first_character == '*':
                # Need to check the 2nd digit
                for i in range(1, 3):
                    if i == 2 and int(second_character) > 6:
                        continue
                    recursive_decode(current_index + 2, current_decoding + str(i) + second_character)

            elif second_character == '*':
                # Need to check the 1st digit
                if first_character == '1':
                    for i in range(0, 10):
                        recursive_decode(current_index + 2, current_decoding + first_character + str(i))
                elif first_character == '2':
                    # '*' can be 0-6 if the first digit is 2
                    for i in range(0, 7):
                        recursive_decode(current_index + 2, current_decoding + first_character + str(i))
            
            else:
                two_character = int(first_character + second_character)
                if 10 <= two_character <= 26:
                    # Valid two-character decoding
                    recursive_decode(current_index + 2, current_decoding + str(two_character))

    #Initiate our recursive calls
    recursive_decode(0, "")

    # Return the answer
    return number_of_ways

Big(O) Analysis

Time Complexity

O(2^n) – The approach described is a brute force exploration of all possible decodings, essentially trying every combination. In the worst-case scenario, where most single digits and pairs of digits can be decoded, the algorithm branches at each digit. This branching leads to an exponential number of paths being explored. The number of operations grows exponentially with the length of the input string n, resulting in a time complexity of O(2^n).

Space Complexity

O(N) – The described brute-force approach involves exploring all possible decoding combinations, which implicitly uses a recursion stack. In the worst-case scenario, the recursion depth can reach N, where N is the length of the input string, as it explores decoding each character or pair of characters. Thus, the space used by the recursion stack grows linearly with the input size. No other significant auxiliary data structures are used, so the space complexity is dominated by the recursion stack.

Optimal Solution

Approach

The problem involves decoding a message represented by digits and asterisks. The efficient solution figures out the number of possible decodings by building up from smaller sub-problems, reusing previously calculated answers to avoid redundant work and handling asterisks smartly.

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

Start at the beginning of the encoded message and consider each digit or asterisk one at a time.
For each position, figure out how many ways you can decode the current character by itself.
Also, look at the current character and the one before it together. Figure out how many ways you can decode these two characters as a pair.
Remember to handle the special case of the asterisk. Since it can represent any digit, consider all possibilities that it could be (1-9) when decoding it by itself, or (1-9) when decoding it as a pair with a preceding digit and/or another asterisk.
To avoid repeated calculations, keep track of the number of ways to decode up to each position in the message. The number of ways to decode up to the current position is based on the number of ways to decode up to the previous position (when considering a single character) and the number of ways to decode up to the position before the previous one (when considering a pair of characters).
Keep building up these counts until you reach the end of the message. The final count is the number of ways to decode the entire message.
Since the numbers can get very big, remember to take the result modulo a large prime number at each step to prevent integer overflow.

Code Implementation

def decode_ways_two(encoded_string):
    modulo = 10**9 + 7
    string_length = len(encoded_string)
    number_of_ways = [0] * (string_length + 1)
    number_of_ways[0] = 1

    for i in range(1, string_length + 1):
        #Calculate ways based on single character
        one_digit = encoded_string[i-1]
        if one_digit == '*':
            number_of_ways[i] = (number_of_ways[i] + 9 * number_of_ways[i-1]) % modulo
        elif one_digit != '0':
            number_of_ways[i] = (number_of_ways[i] + number_of_ways[i-1]) % modulo
        
        #Calculate ways based on two characters
        if i > 1:
            two_digits = encoded_string[i-2:i]
            if two_digits[0] == '*' and two_digits[1] == '*':
                number_of_ways[i] = (number_of_ways[i] + 15 * number_of_ways[i-2]) % modulo
            elif two_digits[0] == '*':
                if two_digits[1] <= '6':
                    number_of_ways[i] = (number_of_ways[i] + 2 * number_of_ways[i-2]) % modulo
                else:
                    number_of_ways[i] = (number_of_ways[i] + number_of_ways[i-2]) % modulo
            elif two_digits[1] == '*':
                #Need to check if the number is between 10 and 26
                if two_digits[0] == '1':
                    number_of_ways[i] = (number_of_ways[i] + 9 * number_of_ways[i-2]) % modulo
                elif two_digits[0] == '2':
                    number_of_ways[i] = (number_of_ways[i] + 6 * number_of_ways[i-2]) % modulo
            else:
                #Need to check if the number is between 10 and 26
                two_digit_value = int(two_digits)
                if 10 <= two_digit_value <= 26:
                    number_of_ways[i] = (number_of_ways[i] + number_of_ways[i-2]) % modulo

    # Modulo operator prevents integer overflow
    return number_of_ways[string_length] % modulo

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the encoded message once, where n is the length of the message. For each position, it performs a constant amount of work involving calculating single and double character decodings, including handling asterisk cases. Since the number of operations per position is constant and independent of n, the total time complexity is directly proportional to the length of the message, resulting in O(n).

Space Complexity

O(N) – The solution uses dynamic programming to build up the number of ways to decode the message. It keeps track of the number of ways to decode up to each position in the message, storing these counts in a data structure, typically an array or a list. Therefore, the algorithm requires an auxiliary array (or list) to store intermediate results, where the size of this array is directly proportional to the length of the input message. This results in an auxiliary space usage of O(N), where N is the length of the input string.

Edge Cases

Case	How to Handle
Null or empty string input	Return 1 if the string is empty, as there is one way to decode an empty string.
String starts with '0'	Return 0 immediately, as a '0' cannot be decoded alone.
String contains consecutive '**' sequences	Correctly calculate the number of ways to decode '**' as 15.
String contains a single '*'	Correctly handle '*' as representing digits 1-9, so it represents 9 ways.
String contains invalid sequences like '01', '02', etc.	Treat these as invalid and return 0 possibilities for that branch.
String contains a very long sequence of '1's	Use dynamic programming with modulo operation to prevent integer overflow.
String contains '1' or '2' sequences	Handle '1' as 9 possibilities (11-19) and '2' as 6 possibilities (21-26).
Large input string causing integer overflow	Apply the modulo operator (10^9 + 7) at each step to keep the result within the integer range.

Null or empty string input

How to Handle:

Return 1 if the string is empty, as there is one way to decode an empty string.

String starts with '0'

How to Handle:

Return 0 immediately, as a '0' cannot be decoded alone.

String contains consecutive '**' sequences

How to Handle:

Correctly calculate the number of ways to decode '**' as 15.

String contains a single '*'

How to Handle:

Correctly handle '*' as representing digits 1-9, so it represents 9 ways.

String contains invalid sequences like '01', '02', etc.

How to Handle:

Treat these as invalid and return 0 possibilities for that branch.

String contains a very long sequence of '1's

How to Handle:

Use dynamic programming with modulo operation to prevent integer overflow.

String contains '1*' or '2*' sequences

How to Handle:

Handle '1*' as 9 possibilities (11-19) and '2*' as 6 possibilities (21-26).

Large input string causing integer overflow

How to Handle:

Apply the modulo operator (10^9 + 7) at each step to keep the result within the integer range.