Comment on page
91 Decode Ways
A message containing letters from
A-Z
is being encoded to numbers using the following mapping:'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message
"12"
, it could be decoded as"AB"
(1 2) or"L"
(12).The number of ways decoding
"12"
is 2.The Idea: This problem can be reduced to solving subproblems. For example, the input
12345
can be reduced to solving numDecodings(12345) = numDecodings(1234) + numDecodings(123)
. The way to interpret this is that the tail end of the input 5
and 45
can interpreted to have two unique encodings. In this case of course, 45
would return 0 because it is out of bounds of the alphabetical mapping [1-26]
. There are also a few other edge cases to consider, and I have highlighted then in the recursion trees below. The general idea is to not descend down a subtree if the interpretation of the tail end of the string isn't valid.You may also notice some reoccurring subtrees, in which case, we use memiozation to save their results.



Complexity: O(N) time and space
class Solution:
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
# memoization
memo = {}
# helper DFS (preorder)
def __numDecodings(s, n):
# if the front string is empty return 1 (leaf node in tree)
if not s:
return 1
# check if in memory
elif s in memo:
return memo[s]
# otherwise perform recursion
else:
# only decend down tree if we can at least get empty string from s
result1, result2 = 0, 0
if n:
# car and cdr
front1 = s[0:n - 1]
tail1 = s[n - 1:]
# there is no way to interpret 0 as a valid answer
result1 = 0 if tail1 == '0' else __numDecodings(front1, n - 1)
if n-1:
# same idea, but now interpret 2 digits
front2 = s[0:n - 2]
tail2 = s[n - 2:]
# there is no way to interpret a valid solution if the
# number exceeds 26, or if the tail starts with 0 (consider edge case '101')
result2 = 0 if not (1 <= int(tail2) <= 26) or tail2[0] == '0' else __numDecodings(front2, n - 2)
memo[s] = result1 + result2
return memo[s]
return __numDecodings(s, len(s))
Last modified 4yr ago