Description:
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Solutions:
Solution1: brute force DFS
TLE at "9371597631128776948387197132267188677349946742344217846154932859125134924241649584251978418763151253"
class Solution:
def numDecodings(self, s: str) -> int:
if not s:
return 0
seq_ls = []
count = 0
def dfs(seq):
nonlocal count
nonlocal seq_ls
if seq == len(s):
# print(seq_ls)
count += 1
elif seq == len(s)-1:
if s[seq] != "0":
# print(seq_ls+[seq])
count += 1
elif seq < len(s)-1:
if s[seq] != "0":
seq_ls.append(seq)
dfs(seq+1)
seq_ls.pop()
# print("+2:",int(s[seq:seq+2]))
if int(s[seq:seq+2]) < 27 and int(s[seq:seq+2]) > 0:
seq_ls.append(seq)
dfs(seq+2)
seq_ls.pop()
dfs(0)
return count
Solution2: hash table递归
class Solution:
def numDecodings(self, s: str) -> int:
if not s:
return 0
dic = {}
def dfs(seq):
if seq in dic:
return dic[seq]
if seq == len(s): # last two is okay
return 1
elif seq == len(s)-1 and s[seq] != "0": # last one should not be "0"
return 1
elif seq < len(s)-1 and s[seq] != "0": # before the last one, the first should not be "0"
dic[seq] = dfs(seq+1) # move 1 step
if int(s[seq:seq+2]) < 27 and int(s[seq:seq+2]) > 0: # move 2 steps
dic[seq] += dfs(seq+2)
return dic[seq]
else:
return 0
return dfs(0)
Runtime: 36 ms, faster than 85.82% of Python3 online submissions for Decode Ways.
Memory Usage: 14.4 MB, less than 12.55% of Python3 online submissions for Decode Ways.
sample 20 ms submission: 递推(实际上在测试集上并不比递归更快，估计len(s)没有太大)
class Solution:
def numDecodings(self, s: str) -> int:
if not s or len(s) == 0:
return 0
# dp[i]: the number of decode ways ending at index i
dp = [0] * (len(s) + 1)
dp[0] = 1 # empty
dp[1] = 1 if s[0] != "0" else 0 # s[0:1]
for i in range(2, len(s) + 1):
prev1 = s[i - 1: i]
prev2 = s[i - 2: i]
if 1 <= int(prev1) <= 9: # easy to understand
dp[i] += dp[i - 1]
if 10 <= int(prev2) <= 26:
# if using 0 < int(prev2) < 27, OJ will report an wrong answer when input == "01"
dp[i] += dp[i - 2]
return dp[-1]
