Decode Message - Algorithms

Decode Message.md

Decode Message

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message message (as a string), count the number of ways it can be decoded.
For example, the message 111 should return 3, since it could be decoded as aaa, ka, and ak.
You can assume that the messages are decodable. For example, 001 is not a valid input.

Example 1

Input

message = "111"

Output 3 Explanation This can be decoded 3 ways: aaa, ak, and ka.

Example 2

Input

message = "8" 

Output 1 Explanation
This can be only decoded one way, as h.

Example 3

Input

message = "12" 

Output 2

Explanation
This can be decoded 2 ways: ab or l.

solution.py

import string 

dmap = dict(
    zip(range(1,27), string.ascii_lowercase)
)
class Solution:
    
    def solve(self, message):
        # Write your code here
        arr = [0] * len(message)
        
        # Initialization
        arr[-1] = 1
        if len(message) > 1:
            arr[-2] = 2 if int(message[-2:]) in dmap else 1
        
        # Fill the array
        for i in reversed(range(len(message) - 2)):
            into = int(message[i:i+2]) in dmap
            arr[i] = arr[i+1] + (arr[i+2] if into else 0)
        
        return arr[0]