解码方法

问题简述

将数字解码成字母，返回可能的解码方法数；
例如，"11106" 可以映射为：
    "AAJF" ，将消息分组为 (1 1 10 6)
    "KJF" ，将消息分组为 (11 10 6)

91. 解码方法 - 力扣（LeetCode）

思路

• 有限制的 "跳台阶" 问题: dp[i] = dp[i-1] + dp[i-2];

  • 只有当 s[i] 和 s[i-1] 满足某些条件时, 才能从 dp[i-1] 或 dp[i-2] "跳上来";

Python: 递归写法

class Solution:
    def numDecodings(self, s: str) -> int:

        from functools import lru_cache

        @lru_cache
        def dfs(i):  # 前 i 个字符的解码方法数
            # 最容易出错的点, 以 0 开头的字符串不存在相应的编码
            if i <= 1: return int(s[0] != '0')

            ret = 0
            if '1' <= s[i - 1] <= '9':  # 如果 s[i] 在 0~9, 存在相应的编码
                ret += dfs(i - 1)  # s[i-1] == 1 和 s[i-2] 的特殊讨论
            if s[i - 2] == '1' or s[i - 2] == '2' and '0' <= s[i - 1] <= '6':
                ret += dfs(i - 2)
            
            return ret
        
        return dfs(len(s))

Python: 迭代写法 (与递归版一一对应)

class Solution:
    def numDecodings(self, s: str) -> int:
        
        # if s[0] == '0': return 0

        dp = [0] * (len(s) + 1)
        # dp[0] = dp[1] = int(s[0] != '0')
        
        # 注意 i 的范围与递归中一致
        for i in range(len(s) + 1):
            # 下面就是把递归中的代码搬过来
            if i <= 1:  # 如果把这一段拿到循环外, 需要调整 i 的遍历范围
                dp[i] = int(s[0] != '0')
                continue
            dp[i] = 0
            if '1' <= s[i - 1] <= '9':
                dp[i] += dp[i - 1]
            if s[i - 2] == '1' or s[i - 2] == '2' and '0' <= s[i - 1] <= '6':
                dp[i] += dp[i - 2]
        
        return dp[-1]