Skip to content

Instantly share code, notes, and snippets.

@maelfosso
Last active July 29, 2020 21:46
Show Gist options
  • Save maelfosso/79911b47926a8c3808bcbf4eba5f5593 to your computer and use it in GitHub Desktop.
Save maelfosso/79911b47926a8c3808bcbf4eba5f5593 to your computer and use it in GitHub Desktop.
Decode Message - Algorithms

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.

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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment