原题
有一个消息包含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)]
