19.解码方法

题目描述：一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的非空字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。

示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6)或者"BBF" (2 2 6) 。

示例 3：
输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

示例 4：
输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

解题思路：形如：s='22610'。
初始化：f[0]=1,
计算f[1]:
s[0]='2' -> '2' -> f[0]分成的子序列+'2' -> f[1]=1 （【f[0]分成的子序列 | '2' 】表示在字符串‘2’合法的情况下f[0]能分成多少子序列）
计算f[2]:
s[1]='2',s[0]='2' -> "2,2' or '22' -> f[1]分成的子序列 | '2' or f[0]分成的子序列 | '22' -> f[2]=1+1
计算f[3]:
s[2]='6'.s[1]='2',s[0]='2' -> '2,2,6' or '22,6' or '2,26' -> f[1]分成的子序列 | '6' or f[0]分成的子序列 | '26' -> f[3]=2+1
计算f[4]:
s[3]='1',s[2]='6'.s[1]='2',s[0]='2' -> '2,2,6,1' or '22,6,1' or '2,26,1'or'2,2,61' or '22,61' or '2,261' -> f[1]分成的子序列 | '1' or f[0]分成的子序列 | '61' -> f[4]=3+0
计算f[5]:
s[4]='0',s[3]='1',s[2]='6'.s[1]='2',s[0]='2' -> '2,2,6,1,0' or '22,6,1,0' or '2,26,1,0'or'2,2,6,10' or '22,6,10' or '2,26,10' -> f[4]分成的子序列 | '0' or f[3]分成的子序列 | '10' -> f[5]=0+3
我们观察可以发现，s[i]能分多少类取决于他的前两项能分多少类以及他自身是否合法以及他与前一个字符的拼接是否合法。我们为什么只考虑前两项也很好理解，因为 s[i]至多能和s[i-1]进行拼接得到合法的匹配值key（1<=key<=26)，再往前考虑key必定会非法（key>26）。
因此我们可以写出状态转移函数： f[i]=f[i-1] | s[i] + f[i-2] | s[i-1:i+1]

class Solution:
    def numDecodings(self, s: str) -> int:
        spre,pre,cur=0,1,0
        for i in range(len(s)):
            cur=0
            if s[i]!='0':
                cur=pre #pre代表i项和i-1项是否能组合成功
            if i-1>=0 and s[i-1]!='0' and int(s[i-1]+s[i])<=26:
                cur+=spre  #spre代表i之前项可能的组合方式
            if cur==0:
                return 0
            pre,spre=cur,pre 
        return cur

作者：lan-mao-xiao-ge-ge
链接：https://leetcode-cn.com/problems/decode-ways/solution/ri-geng-zui-ben-de-mei-ri-yi-ti-jie-fa-z-hace/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。