leetcode解码方法（动态规划python）

描述

有一个消息包含A-Z通过以下规则编码

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
现在给你一个加密过后的消息，问有几种解码的方式

我们不能解码空串，因此若消息为空，你应该返回0。
消息的长度 n \leq 100n≤100

您在真实的面试中是否遇到过这个题？
样例
样例 1:

输入: “12”
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).
样例 2:

输入: “10”
输出: 1

思路
动态规划，从s的位置1读起，每次读取两个数，因为只要是1-9的数，都可以单独出现，因此，dp表可以初始化为1，为了避免第二个条件[i-1]无法执行，我们使得dp表从位置2开始修改，dp位置0，1的值都初始化为1

情况
#特殊情况 输入’’ 则无法解码，可直接返回 0
#输入0 则无法解码，可直接返回 0
#若为 00 或 30、40、50… 则无法解码，可直接返回 0
#为 10、20 的情况，则 i 处字符必须与前一位结合，则为双字符解码
dp[i + 1] = dp[i - 1]
若数字为10-26：既可以单字解码，又可以双字解码 dp[i + 1] = dp[i] + dp[i - 1]
#1-9，27-29、31-39、41~49…只能单字解码 dp[i + 1] = dp[i]

class Solution:
    def numDecodings(self, s):
        if len(s)==0: return 0 #特殊情况 输入'' 则无法解码，可直接返回 0
        if s[0]=="0":return 0 #输入0 则无法解码，可直接返回 0
        dp = [0] * (len(s) + 1)
        dp[0],dp[1]=1,1

        for i in range(1, len(s)):
            if s[i] == '0':
                if int(s[i - 1]) > 2 or int(s[i - 1]) == 0: #若为 00 或 30、40、50... 则无法解码，可直接返回 0；
                    return 0
                dp[i + 1] = dp[i - 1] #为 10、20 的情况，则 i 处字符必须与前一位结合，则为双字符解码
            elif 9 < int(s[i - 1:i + 1]) < 27:
                dp[i + 1] = dp[i] + dp[i - 1] #既可以单字解码，又可以双字解码
            else:
                dp[i + 1] = dp[i]#1-9，27~29、31~39、41~49....只能单字解码
        return dp[-1] 
test = Solution()
s_li = ["9", "226", "300"]
for s in s_li:
    print(test.numDecodings(s))

结果：
1
3
0