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]
