※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 91. Decode Ways
: 該題提供一個由數字組成的字串s，並提供我們一個編碼表：
: 'A' -> "1"
: 'B' -> "2"
: ...
: 'Z' -> "26"
: 求出s共有幾種編碼的方式，若無法被編碼出來返回0。
: Example：
: Input: s = "12"
: Output: 2
: Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
思路:
1.爬樓梯的變化版 爬樓梯就是給你階梯長度 你一次能爬一階或兩階 問你有幾種爬法
問就是 f(n) = f(n-1) + f(n-2), f(0) = f(1) = 1
2.所以這題也是差不多 一次選一個數字或兩個數字 只是要多檢查合不合法
dp[i] = dp[i+1] + dp[i+2] dp[i]代表從i往下的字串有幾種 decode 方法
如果自己是0 -> 不能 decode 0開頭的數字 一定不合法 爬法是0
如果自己是1~9 -> 一次選一個的操作合法 可以加上dp[i+1]
如果自己和下一個 < 27 -> 一次選兩個的操作合法 可以加上dp[i+2]
3.dp要加長一下 寫起來比較方便
因為在算dp[len(s)-2] 的時候 沒有dp[len(s)]給你加
簡單判斷掉也可以
Python code:
class Solution:
def numDecodings(self, s: str) -> int:
dp = [0]*(len(s)+1)
dp[-1], dp[-2] = 1, 0 if s[-1] == '0' else 1
for i in range(len(s)-2, -1, -1):
if s[i] == '0':
dp[i] = 0
else:
dp[i] = dp[i+1] + (dp[i+2] if int(s[i:i+2]) < 27 else 0)
return dp[0]