原題
有一個消息包含A-Z通過以下規(guī)則編碼
'A' -> 1
'B' -> 2
...
'Z' -> 26
現(xiàn)在給你一個加密過后的消息颗圣，問有幾種解碼的方式
樣例
給你的消息為12，有兩種方式解碼 AB(12) 或者 L(12). 所以返回 2
解題思路
- 求有幾種解碼方式而不是具體每種解碼方式是什么 - 動態(tài)規(guī)劃 - Sequence DP
- cache[i]表示以第i個字符結(jié)尾的字符串有幾種解碼方式
- 初始化
- cache[0] = 1 空字符串認(rèn)為有是一種解碼方式
- cache[1] = 1 一個字符肯定只有一種解法方式 (最開始記得判斷第一個字符是0返回0種解碼方式)
- 狀態(tài)轉(zhuǎn)移方程，cache[i] 要考慮和上一位組成的數(shù)字具體是多少
- 如果是00，30舌菜，40萌壳，50亦镶，60，70袱瓮，80缤骨，90 => cache[i] = 0 (無解) s[i - 1]如果是0要仔細(xì)考慮
- 如果是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)]
