The Blind 75 Leetcode Series: Decode Ways

Photo by Chris Ried on Unsplash

Today, we are working on 91. Decode Ways

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

Given a string s containing only digits, return the number of ways to decode it.

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

We have a string of digits, and we are trying to map them into alphabets by mapping each digit (or 2 digits) to the corresponding uppercase letter. We return number of ways we can interpret them.

We want to cover some corner cases first:

1. do we expect empty string? What do we return?
2. Do we expect leading 0's?

If the interviewer tells us that we do expect empty strings and leading zeros, and we should return 1 for empty string and 0 for leading 0, then we know that

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). We may have empty strings which we should return 1 way to interpret (which we should interpret it as “empty”), and we may see leading 0’s. (Which there’s no way to interpret the string and should return 0)

Let’s start.

The intuition is that we should be able to build it up from a shorter string. answer to “11” should help us to find answer for “111”.

This is with one exception which we have to consider 2 digits, which we have to bring one previous digit to include in the calculation.

Using the same example above, “11” should return 2 since we have “AA(1, 1)” and “K(11)” as answers. Once we bring in that extra “1”, we now can decode “111” into “AAA(1, 1, 1)”, “KA (11, 1)”, and “AK(1, 11)”. As you can see, we have to consider the case when we combine the last 1 from the “11” and the new “1”.

Another curve ball is the digit “0”. We cannot have “0” as leading number, and “0” itself does not represent any letter, so we have to make sure “0” is only considered for the 2-digit case.

If we can take care of these cases, we can use the build-it-up method, which seems like a good job for dynamic programming.

We first build a list of 0’s, representing the number of ways to decode each segment of string.

decode_ways = [0] * len(s) + 1

s is the original string of digits. We want to add an additional element to represent the empty string.

Now we can initialize the base cases for empty string and length = 1 strings.

decode_ways[0], decode_ways[1] = 1, 0 if s[0] == '0' else 1

decode_ways[0] is the empty string case, and decode_ways[1] is the length = 1 case. We want to make sure it’s not with the leading 0.

Now that we covered the base cases, we can continue to build from here. We start from 3rd digit (or index = 2 for 0th idx base).

• For 1-digit case, we check if the digit falls between 1 and 9. We do not count 0 as 0 itself does not map to anything. If so, we add the decode_ways[i-1] to the current decode_ways[i].
• For 2-digit case, we combine the current digit with the previous digit in s and check if it falls between 10 (J) and 26 (Z). If that’s the case, we add decode_ways[i-2] to current decode_ways[i].

If you’ve been following this series, you’ll notice that this problem now looks a lot like the Climbing Stairs problem.

When we have gone through the entire string, we return the last element of the decode_ways to show us the number of ways to decode the entire string.

Let’s put it into code:

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

What’s the time complexity for this? We’ve gone through the string once and only once, so the time spent depends on the length of s thus giving us a time complexity of O(n).

Do we have another approach? Since we used the build-up method to build an answer list for all substring, can we do the same by breaking the problem into smaller sub problem and work our way to the original problem?

We check the leading digit and leading 2 digits with the same conditions as the dynamic programming approach, and we pass in the rest of the string into the same same checking conditions again. This seems like a job for recursion.

We first form the base condition, which is simply returning 1 if we don’t see any string. Then from there, we pass in either s[1:] or s[2:] into the same function based on which condition you check.

So the recursive function looks like:

def recursion(s):
    # empty string case
    if not s:
        return 1
    single_digit_way, double_digit_way = 0, 0
    if int(s[0]) > 0 and int(s[0]) <= 9:
        single_digit_way += recursion(s[1:])
    if int(s[:2]) >= 10 and int(s[:2]) <= 26:
        double_digit_way += recursion(s[2:])
    return single_digit_way + double_digit_way

This recursive function returns the result of single digit call and double digit call summed together. Each call checks for the single digit and double digit calls again. The result then sums up at the end.

Now we just need to make the root function call the recursive.

def numDecodings(s):
    if s and s[0] == '0':
        return 0
    return recursion(s)

Note that this approach works but actually times out on Leetcode. This is due to having too many snapshots (each recursion creates a snapshot).

To solve this problem, we want to pass in a tracker so that we can retrieve the result we’ve already seen fast instead of calling the recursive again. For every recursive function called, we store the result of single_digit_way + double_digit_way in the tracker.

...
if s in tracker:
    return tracker[s]  # return stored result
...
tracker[s] = single_digit_way + double_digit_way  # store the result of calls to tracker
return single_digit_way + double_digit_way

Now the function looks like

def recursion(s, tracker):
    # empty string case
    if not s:
        return 1
    if s in tracker:
        return tracker[s]
    single_digit_way, double_digit_way = 0, 0
    if int(s[0]) > 0 and int(s[0]) <= 9:
        single_digit_way += recursion(s[1:])
    if int(s[:2]) >= 10 and int(s[:2]) <= 26:
        double_digit_way += recursion(s[2:])
    tracker[s] = single_digit_way + double_digit_way
    return single_digit_way + double_digit_way
def numDecodings(s):
    if s and s[0] == '0':
        return 0
    dp = {}
    return self.recursion(s, dp)

What’s the time complexity now?

We are still going through the same string, so the time complexity stays at O(n).

That’s it. Another problem down.

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz