原题

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

'A' -> 1
'B' -> 2
...
'Z' -> 26

现在给你一个加密过后的消息，问有几种解码的方式

样例
给你的消息为12，有两种方式解码 AB(12) 或者 L(12). 所以返回 2

解题思路

• 求有几种解码方式而不是具体每种解码方式是什么 - 动态规划 - Sequence DP
• cache[i]表示以第i个字符结尾的字符串有几种解码方式
• 初始化
• cache[0] = 1 空字符串认为有是一种解码方式
• cache[1] = 1 一个字符肯定只有一种解法方式 (最开始记得判断第一个字符是0返回0种解码方式)
• 状态转移方程，cache[i] 要考虑和上一位组成的数字具体是多少
• 如果是00，30，40，50，60，70，80，90 => cache[i] = 0 (无解) s[i - 1]如果是0要仔细考虑
• 如果是01~09，比如，1501 => 150有几种解(因为0单独不会有解)
• 如果是10~26其中不包括10，20的话，则有两种情况，比如1512 => 15有几种解(L) + 151有几种解(B)
• 如果等于10或者20，比如，1510 => 15有几种解(因为0单独不会有解, J(10)/T(20))
• 如果大于26，比如，1527 => 152有几种解

完整代码

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or s[0] == "0":
            return 0
            
        cache = [0 for i in range(len(s) + 1)]
        cache[0] = cache[1] = 1
        for i in range(2, len(s) + 1):
            num = int(s[i-2:i])
            if num == 0 or (s[i - 1] == "0" and num > 26): # 100 or 130
                cache[i] = 0
            elif num < 10: # 109
                cache[i] = cache[i - 1]
            elif num < 27: 
                if num == 10 or num == 20: # 110 or 120
                    cache[i] = cache[i - 2]
                else: # 117, 126 ...
                    cache[i] = cache[i - 1] + cache[i - 2]
            else: # 127, 178
                cache[i] = cache[i - 1]
                
        return cache[len(s)]