Day #7: Number of possible decodable messages

Day #7: Number of possible decodable messages

Hello everyone. Today is the Day 7 of the #100DaysOfCodeChallenge. And it's a week!!!! Received a problem previously asked by Facebook with a hard tag to it.

The Question On Day #6:

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.

Algorithm

  • The algorithm is similar to the concept behind fibonacci series. For every increase in the value of n is fibonacci we added it to the n-1 sum.
  • Similarly, for every increase in the length of the message, we add a particular value to the number of possible ways, based on certain conditions.
  • Points to check:
    • a 1-digit number is considered a message only if it is greater than 0, because a is represented by 1 according to the question.
    • a 2-digit number is considered a message only if it has 2 in the ten's place and digit<7 in the one's place or 1 in ten's place and any digit in one's place.

Python Code

Output Number Of Ways: 3

Visualiser

You can look into the visualiser to understand the BTS of the logic here.

Feel free to reach out for any query clearance.

Thanks and cheers:)