欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode解码方法(动态规划python)

程序员文章站 2022-07-05 18:18:48
...

描述

有一个消息包含A-Z通过以下规则编码

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
现在给你一个加密过后的消息,问有几种解码的方式

我们不能解码空串,因此若消息为空,你应该返回0。
消息的长度 n \leq 100n≤100

您在真实的面试中是否遇到过这个题?
样例
样例 1:

输入: “12”
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).
样例 2:

输入: “10”
输出: 1

思路
动态规划,从s的位置1读起,每次读取两个数,因为只要是1-9的数,都可以单独出现,因此,dp表可以初始化为1,为了避免第二个条件[i-1]无法执行,我们使得dp表从位置2开始修改,dp位置0,1的值都初始化为1

情况
#特殊情况 输入’’ 则无法解码,可直接返回 0
#输入0 则无法解码,可直接返回 0
#若为 00 或 30、40、50… 则无法解码,可直接返回 0
#为 10、20 的情况,则 i 处字符必须与前一位结合,则为双字符解码
dp[i + 1] = dp[i - 1]
若数字为10-26:既可以单字解码,又可以双字解码 dp[i + 1] = dp[i] + dp[i - 1]
#1-9,27-29、31-39、41~49…只能单字解码 dp[i + 1] = dp[i]

class Solution:
    def numDecodings(self, s):
        if len(s)==0: return 0 #特殊情况 输入'' 则无法解码,可直接返回 0
        if s[0]=="0":return 0 #输入0 则无法解码,可直接返回 0
        dp = [0] * (len(s) + 1)
        dp[0],dp[1]=1,1

        for i in range(1, len(s)):
            if s[i] == '0':
                if int(s[i - 1]) > 2 or int(s[i - 1]) == 0: #若为 00 或 30、40、50... 则无法解码,可直接返回 0;
                    return 0
                dp[i + 1] = dp[i - 1] #为 10、20 的情况,则 i 处字符必须与前一位结合,则为双字符解码
            elif 9 < int(s[i - 1:i + 1]) < 27:
                dp[i + 1] = dp[i] + dp[i - 1] #既可以单字解码,又可以双字解码
            else:
                dp[i + 1] = dp[i]#1-9,27~29、31~39、41~49....只能单字解码
        return dp[-1] 
test = Solution()
s_li = ["9", "226", "300"]
for s in s_li:
    print(test.numDecodings(s))

结果:
1
3
0