Daily Coding Problem: Problem #7

Photo by XPS on Unsplash

Here I am with another problem!.

Problem

Given the mapping a = 1, b = 2, … z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message ‘111’ would give 3, since it could be decoded as ‘aaa’, ‘ka’, and ‘ak’.

You can assume that the messages are decodable. For example, ‘001’ is not allowed.

Trying to apply brute force approach here can be a little harder. Well I didn’t think of the brute force approach first. The initial thought process of mine after looking at the problem is to solve it using sub-problems. For example, let the encoded message be 12345 . The problem can be divided into two parts.

1 + 2345 and 12 + 345

Here 1 translates to a and 12 translates to l .

But the problem cannot be always divided into two sub-problems. Consider the case 3345 . Here if we divide the problem into two parts, we get

3 + 345 and 33 + 45

But 33 translates to nothing. The permissible range is [1,26] . So this can be solved recursively. Since we are solving it recursively, let’s find our base conditions.

1. If we get an empty string '' we return 1 because, an empty encoded string translates to an empty string.
2. If we find any 0 in our encoded string, we return 0 as 0 translates to nothing.

With all this, let try out our first solution. We use a helper function helper and variable k to avoid modifying the input data .

Solution 1: Recursion

Python:

Go:

If we observe closely, our solution is similar to the fibonacci solution. Since it is the same our time complexity is also similar to it which is O(2^n). This can be easily solved using Dynamic Programming and memoization. Don’t get scared by looking at these fancy words. The problem with our solution is that we are recomputing the already computed sub-problems. Doing so increases our computing time. One way to tackle is by storing our previously computed solution and using it when the same problem appears again. This way our solution won’t be spending time in re-computing.

Solution 2: Memoization

Python:

Go:

Time Complexity: O(n)

Space Complexity: O(n)

I hope you guys enjoyed this post.

If you find it helpful, please share and claps are much appreciated! 😄

Feel to ask your queries in the comments section!.