Comment on page
91 Decode Ways
A message containing letters from
A-Zis 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