[Leetcode][python]Decode Ways/解码方法-蒲公英云

[Leetcode][python]Decode Ways/解码方法

冷不防 2022-06-06 04:13 250阅读 0赞

题目大意

现在有如下的字母与数字的对应关系：1-A, 2-B, …26-Z。给定一个由数字组成的字符串，判断按照上面的映射可以转换成多少种不同的字符串。

解题思路

动态规划
参考：http://www.cnblogs.com/zuoyuan/p/3783897.html

和爬梯子相当像，但需要分情况考虑而不能一味dp[i]=dp[i-1]+dp[i-2]
解码有多少种方法。一般求“多少”我们考虑使用dp。状态方程如下：

当s[i-2:i]这两个字符是10~26但不包括10和20这两个数时，比如21，那么可以有两种编码方式（BA，U），所以dp[i]=dp[i-1]+dp[i-2]
当s[i-2:i]等于10或者20时，由于10和20只有一种编码方式，所以dp[i]=dp[i-2]
当s[i-2:i]不在以上两个范围时，如09这种，编码方式为0。
而31这种，dp[i]=dp[i-1]。

注意初始化时：dp[0]=1,dp[1]=1

举个例子：

123421
[1, 1] 
[1, 1, 2] 12
[1, 1, 2, 3] 23
[1, 1, 2, 3, 3] 34
[1, 1, 2, 3, 3, 3] 42
[1, 1, 2, 3, 3, 3, 6] 21

首先12，有两种可能，所以dp[3]=1+1
然后23，两种可能，所以1+2 = 3
然后34，从全局看，123多了4之后由于不能和前面的组成新组合，只能自己独立，所以可能输并不会变化
42和34一样理解，不增加新可能。
到了21，由于其有两种可能，那么使得之前的都会累积成为新变种，所以是dp[i]=dp[i-1]+dp[i-2]，这一步是最重要的

代码

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == "" or s[0] == "0": 
            return 0
        if len(s) == 1:
            return 1
        dp = [1,1]
        for i in range(2, len(s)+1):
            # print dp, s[i-2:i]
            if 10 <= int(s[i-2:i]) <= 26 and s[i-1] != '0': # 当s[i-2:i]这两个字符是10~26但不包括10和20这两个数时，比如21，那么可以有两种编码方式（BA，U），所以dp[i]=dp[i-1]+dp[i-2]
                dp.append(dp[i-1]+dp[i-2])
            elif int(s[i-2:i]) == 10 or int(s[i-2:i]) == 20:
                dp.append(dp[i-2])  # 当s[i-2:i]等于10或者20时，由于10和20只有一种编码方式，所以dp[i]=dp[i-2]
            elif s[i-1]!='0':  # 
                dp.append(dp[i-1])  # 当s[i-2:i]不在以上两个范围时，如09这种，编码方式为0，而31这种，dp[i]=dp[i-1]
            else:
                return 0
        return dp[-1]