DP还是比dfs效率高多了啊
class Solution:
def numDecodings(self, s: str) -> int:
def numDecodings(s):
# s = s.lstrip("0")
if s == "":
return [0]
if s[0] == '0':
return [0]
dp = [0 for i in range(len(s) + 1)]
for i in range(len(dp)):
if i == 0:
dp[i] = 1
continue
if i == 1:
dp[i] = 1
continue
if s[i - 1] == '0':
if int(s[i - 2:i]) > 26 or int(s[i - 2:i]) <= 0:
return [0]
else:
dp[i] = dp[i - 2]
else:
if int(s[i - 2:i]) > 26 or int(s[i - 2:i]) <= 0 or s[i - 2] == '0':
dp[i] = dp[i - 1]
else:
dp[i] = dp[i - 1] + dp[i - 2]
return dp
k = numDecodings(s)
return k[-1]
