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

leetcode91.解码方法

程序员文章站 2022-07-05 12:55:28
...

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) 。

2.解题思路

1.递归

2.递归2

3.动态规划

建立一维 dp 数组,其中 dp[i] 表示s中前i个字符组成的子串的解码方法的个数,长度比输入数组长多多1,并将 dp[0] 初始化为1。现在来找状态转移方程,dp[i] 的值跟之前的状态有着千丝万缕的联系,就拿题目中的例子2来分析吧,当 i=1 时,对应s中的字符是 s[0]='2',只有一种拆分方法,就是2,注意 s[0] 一定不能为0,这样的话无法拆分。当 i=2 时,对应s中的字符是 s[1]='2',由于 s[1] 不为0,那么其可以被单独拆分出来,就可以在之前 dp[i-1] 的每种情况下都加上一个单独的2,这样 dp[i] 至少可以有跟 dp[i-1] 一样多的拆分情况,接下来还要看其能否跟前一个数字拼起来,若拼起来的两位数小于等于26,并且大于等于 10(因为两位数的高位不能是0),那么就可以在之前 dp[i-2] 的每种情况下都加上这个二位数,所以最终 dp[i] = dp[i-1] + dp[i-2],是不是发现跟斐波那契数列的性质吻合了。所以0是个很特殊的存在,若当前位置是0,则一定无法单独拆分出来,即不能加上 dp[i-1],就只能看否跟前一个数字组成大于等于 10 且小于等于 26 的数,能的话可以加上 dp[i-2],否则就只能保持为0了。具体的操作步骤是,在遍历的过程中,对每个数字首先判断其是否为0,若是则将 dp[i] 赋为0,若不是,赋上 dp[i-1] 的值,然后看数组前一位是否存在,如果存在且满足前一位是1,或者和当前位一起组成的两位数不大于 26,则当前 dp[i] 值加上 dp[i - 2]。最终返回 dp 数组的最后一个值即可

3.代码实现

1.会超时

class Solution(object):
    def __init__(self):
        self.res = 0
    def isRightNum(self,num):
        if num != str(int(num)):
            return False
        num = int(num)
        if num>=1 and num<=26:
            return True
        else:
            return False
    def dfs(self,s,begin):
        if begin > len(s):
            return
        elif begin == len(s):
            self.res += 1
            return
        for i in range(1,3):
            if self.isRightNum(s[begin:begin+i]):
                self.dfs(s,begin+i)
            
            
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        if s[0]=="0":
            return 0
        self.dfs(s,0)
        return self.res

2.也会超时。。。

class Solution(object):
    def __init__(self):
        self.res = 0
    def isRightNum(self,num):
        if num != str(int(num)):
            return False
        num = int(num)
        if num>=1 and num<=26:
            return True
        else:
            return False
    def dfs(self,s,begin):
        
        if begin == len(s):
            return 1
        elif s[begin] == "0":
            return 0
        ans1 = self.dfs(s,begin+1)
        ans2 = 0
        if begin+2<=len(s):
            if self.isRightNum(s[begin:begin+2]):
                ans2 = self.dfs(s,begin+2)
        return ans1 + ans2
            
            
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        return self.dfs(s,0)

3.动态规划,通过

class Solution(object):
    def isRightNum(self,i,j):
        # 首位不可以为0
        if i == 0:
            return 0
        num=i*10+j
        if num>=1 and num<=26:
            return 1
        else:
            return 0
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        if s[0]=="0":
            return 0
        length=len(s)
        f=[0]*(length+1)
        f[0]=1
        f[1]=1
        for i in range(1,length+1):
            if s[i-1]=="0":
                f[i] = 0
            else:
                f[i] = f[i-1]
            if i>1:
                f[i] += f[i-2]*self.isRightNum(int(s[i-2]),int(s[i-1]))
        return f[length]
            
        
        

 

相关标签: leetcode