Leetcode 91. 解码方法 Decode Ways

目录

1. 递归解法
2. 动态规划

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

递归解法

不用 functools.lru_cache 会超时

import functools
class Solution:
    @functools.lru_cache()
    def numDecodings(self, s: str) -> int:
        if len(s) == 0 or s[0] == '0':
            return 0
        if len(s) == 1:
            return 1
        if len(s) == 2:
            x = 2 if (s[0] == '1' or s[0] == '2' and s[1] < '7') else 1
            if s[1] == '0': x -= 1
            return x
        x = self.numDecodings(s[1:])
        if s[0] == '1' or s[0] == '2' and s[1] < '7':
            x += self.numDecodings(s[2:])
        return x

如果 s 以 0 开头则无法解码，返回 0
（如果 s 不以 0 开头） s 长度为 1 返回 1
长度为 2，有四种情况：既可以作为两个一位数字（都不是 0），也可以作为两位数字，例如 ‘12’。只能作为两个数字，如 ‘32’。只能作为一个两位数，只有两种情况 ‘10’ 、‘20’。无法解析，如 ‘30’。

然后如果长度大于 2 则可以尝试把字符串分成：
第一位和后面的
前两位和后面的（需要前两位构成的数字在 1 - 26 范围内）

动态规划

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

dp[i] 有两种情况：
前一个如果不是 0 就可以累加前一个的值，
如果前一个加当前的值大于 0 且小于 27 可以累加前一个的前一个的值。