解码方法II
思路 动态规划使用dp[0]表示以上个字符作为结尾的方案数 dp[1]表示以当前字符作为结尾的方案数。
于是有nxt_dp[0] dp[1] 而nxt_dp[1]由上个字符结尾方案数 * 当前字符单独解码方案数 上上个字符结尾方案数 * 上个字符与当前字符组合的方案数。
初始化的时候 由于上个字符为空 因此方案数为1 求解当前字符解码方案数即可。
定义一个字典枚举组合 如果方案不出现在字典枚举的组合中 则视为该方案不存在。
class Solution:
one { 1 : 1, 2 : 1, 3 : 1, 4 : 1, 5 : 1, 6 : 1, 7 : 1, 8 : 1, 9 : 1, * : 9}
two { 10 : 1, 11 : 1, 12 : 1, 13 : 1, 14 : 1, 15 : 1, 16 : 1, 17 : 1, 18 : 1,
19 : 1, 20 : 1, 21 : 1, 22 : 1, 23 : 1, 24 : 1, 25 : 1, 26 : 1, *0 : 2,
*1 : 2, *2 : 2, *3 : 2, *4 : 2, *5 : 2, *6 : 2, *7 : 1, *8 : 1, *9 : 1,
1* : 9, 2* : 6, ** : 15}
Mod 10**9 7
def numDecodings(self, s: str) - int:
dp 1, self.one.get(s[:1], 0)
for i in range(1, len(s)):
dp dp[1], (self.one.get(s[i], 0) * dp[1] self.two.get(s[i-1: i 1], 0) * dp[0]) % self.Mod
return dp[-1]
