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

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

## 题目大意 ##

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

## 解题思路 ##

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

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

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

## 总结 ##

[http_www.cnblogs.com_zuoyuan_p_3783897.html]: http://www.cnblogs.com/zuoyuan/p/3783897.html