极客算法

LeetCode-91.解码方法(Decode Ways)


91. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码:

‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 给定一个只包含数字的非空字符串,请计算解码方法的总数。

题目数据保证答案肯定是一个 32 位的整数。

示例 1:

输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。

示例 2:

输入:s = "226"
输出:3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3:

输入:s = "0"
输出:0

示例 4:

输入:s = "1"
输出:1

示例 5:

输入:s = "2"
输出:1

  提示:

1 <= s.length <= 100
s 只包含数字,并且可能包含前导零。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/decode-ways/

Link:https://leetcode.com/problems/decode-ways/

递归 + 记忆化搜索

由于python的强大,加一个lru_cache就可以了

动态规划的本质是,从一个方向递推,防止重复计算,所以递归+记忆化搜索,也是一种动态规划

from functools import lru_cache
class Solution:
    @lru_cache(maxsize=None)
    def numDecodings(self, s: str) -> int:
        if len(s) == 0 or s[0] == '0':
            return 0

        if len(s) == 1 and 1 <= int(s[0]) <= 9:
            return 1

        if len(s) == 2 and 10 <= int(s[0:2]) <= 26:
            return 1 if s[-1] == '0' else 2

        count = 0
        if 1 <= int(s[-1]) <= 9: # 末尾一个字符
            count += self.numDecodings(s[:-1]) # 去掉末尾一个字符
        
        if 10 <= int(s[-2:]) <= 26: #末尾两个字符
            count += self.numDecodings(s[:-2]) # 去掉末尾两个字符

        return count

代码是对称的

from functools import lru_cache
class Solution:
    @lru_cache(maxsize=None)
    def numDecodings(self, s: str) -> int:
        if len(s) == 0 or s[0] == '0':
            return 0

        if len(s) == 1 and 1 <= int(s[0]) <= 9:
            return 1

        if len(s) == 2 and 10 <= int(s[0:2]) <= 26:
            return 1 if s[-1] == '0' else 2

        count = 0
        if 1 <= int(s[0]) <= 9: # 前一个字符
            count += self.numDecodings(s[1:]) # 去掉前一个字符
        
        if 10 <= int(s[:2]) <= 26: # 前两个字符
            count += self.numDecodings(s[2:]) # 去掉前两个字符

        return count

动态规划

状态定义

dp[i]代表前i个字符串有多少种解码方式

状态方程

如果最后数字,可以作为1位数解码(1-9)

table[i] += table[i - 1]

如果最后两位数,可以作为2位数解码(10-26)

table[i] += table[i - 2]

计算方向

从第二个开始,从小到大计算

边界条件

如果第一个数字为0

table[0] = table[1] = 0

相反

table[0] = table[1] = 1

代码实现

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0 for i in range(len(s) + 1)]
        dp[0] = dp[1] = 0 if s[0] == '0' else 1
        
        for i in range(2, len(s) + 1):
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]
                
            if (s[i - 2] == '1' and s[i - 1] in '0123456789') or (s[i - 2] == '2' and s[i - 1] in '0123456'):
                dp[i] += dp[i - 2]
                
        return dp[-1]

–End–


相关推荐

评论

内容: