【leetcode】91. 解码方法

一条包含字母 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) 。

"""

• s[i-2]和s[i-1] 两个字符是10----26之间但不包括10和20这两个数时，

有两种编码方式，比如23------>[“BC”，“W”]，所以dp[i] = dp[i-1]+dp[i-2]

• s[i-2]和s[i-1] 两个字符10或20这两个数时，有一种编码方式，比如10------>[“J”], 所以dp[i] = dp[i-2]
• s[i-2]和s[i-1] 两个字符不在上述两种范围时，编码方式为零，比如27，比如01，所以dp[i] = dp[i-1]

"""

# 实际上有两个约束条件，1. 0不能单独解码 2. 两位数必须在1与26之间。
# 这道题目实际上是用DP去做，仔细想的话，可以发现就是约束版的f(n) = f(n-1) + f(n-2);
# 其中如果是s[n-1]为0，f(n-1) = 0，f(n) = f(n-2)，
# 因为0无法单独解码，而f(n-2)的条件则是必须在1与26之间，否则f(n) = f(n-1)。
class Solution:
    def numDecodings(self, s):
        if s == "" or s[0]=='0': return 0
        dp=[1,1]
        for i in range(2,len(s)+1):
            if 10 <=int(s[i-2:i]) <=26 and s[i-1]!='0':#编码方式为2
                dp.append(dp[i-1]+dp[i-2])
            elif int(s[i-2:i])==10 or int(s[i-2:i])==20:#编码方式为1
                dp.append(dp[i-2])
            elif s[i-1]!='0':#编码方式为0
                dp.append(dp[i-1])
            else:
                return 0
        #print(dp[len(s)])
        return dp[len(s)]

 

参考:

LeetCode 91 Decode Ways (Python详解及实现)

Leetcode 91：解码方法（最详细的解法！！！）