leetcode-91 解码方法

1. 题目内容

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有

2. 基本思路

因为是按照动态规划的题目分类做的，所以从一开始就按照动态规划的模式去思考的。尝试了几个实例时候发现类似斐波那契数列，而且似乎只要一维的dp[]数组即可，本来觉得还算简单，但是没想到被其中无穷无尽的0搞昏了头脑。最终还是参考了高赞题解。
按照滑动窗口的思路进行分析，窗口长度为2，对s进行遍历，窗口中两个数字记为 $a_0$ , $a_1$ 。现在按照 $a_0$ , $a_1$ 是否为0，以及 $a_0a_1$ 是否大于26进行分析：

$a_0 = 0$ 且 $a_1 = 0$ ：一旦字符串中出现连续两个0，将会出现无法解码的情况，因此直接 return 0即可；

$a_0 = 0$ 且 $a_1 \neq 0$ ：此时，考虑 $103$ 这个数， $03$ 只能和前缀组成一种情况，因此此时 $dp[i] = dp[i-2]$ ;

$a_0 \neq 0$ 且 $a_1 = 0$ : 此时要分两种情况：

若 $a_0a_1$ 大于26（即为30 40 50...）,也会出现无法解码的情况，此时return 0；

若 $a_0a_1$ 小于26（即为10或20），这里相当于只有一种情况，不会对总的解码次数产生影响，因此 $dp[i] = dp[i-1]$ ；

$a_0 \neq 0$ 且 $a_1 \neq 0$ ：也需要分两种情况讨论：

若 $a_0a_1$ 小于26，则相当于斐波那契数列，直接 $dp[i] = dp[i-1] + dp[i-2]$ 即可；

若 $a_0a_1$ 大于26，相当于 $a_0、a_1$ 只能分开解码，也对整体解码次数没有影响，因此 $dp[i] = dp[i-1]$ 。

3. 代码实现

class Solution:
    def numDecodings(self, s: str) -> int:
        l = len(s)
        if '00' in s or l == 0 or s[0] == '0':
            return 0
        elif l == 1:
            return l
        dp = [0] * l
        s_num = s[0] + s[1]
        dp[0] = 1
        if s[1] == '0' and int(s_num) > 26:
            return 0
        if int(s_num) > 26 or s[1] == '0':
            dp[1] = 1
        else:
            dp[1] = 2

        for i in range(2, l):
            s_double = int(s[i-1] + s[i])
            if s[i-1] == '0' or (s[i] == '0' and int(s_double) <= 26):
                dp[i] = dp[i-2]
            elif s[i] == '0' and int(s_double) > 26:
                return 0
            elif s_double > 26:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]


if __name__ == '__main__':
    a = Solution()
    b = a.numDecodings('701')
    # print(b)

代码写的比较丑，凑合看吧~

4. 小结

本来以为本题的坑在26这边，避开就好了，殊不知0才是最大的坑，提交错误了八次，好不容易把提交的正确率拉回40%，又白瞎了，心痛。

最后编辑于：2019.08.10 19:10:47