91. 解码方法

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/decode-ways/
Star
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
  • "AAJF" ，将消息分组为 (1 1 10 6)
  • "KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 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
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
示例 4：
输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和"06" 在映射中并不等价）。
提示：
  • 1 <= s.length <= 100
  • s 只包含数字，并且可能包含前导零。
通过次数152,858提交次数502,649

法1 动态规划：时间序列增强型

思路
典型的时间序列类型题目。与爬楼梯相似，当前的状态由上一个状态和上上一个状态决定。按照套路：
  1. 状态定义：
dp[i] : 到第i个字符为止，由多少种解码方法。
  1. 状态转移
  • 如果当前字符能解码出数字，那么dp[i] = dp[i-1]
  • 如果当前字符和上一个字符合起来也能解码出字符，那么dp[i] += dp[i-2]
💡
注：问的是解码方法，而不是能解码出几个不同的字符。所以与爬楼梯基本一样
上楼梯的复杂版 如果连续的两位数符合条件，就相当于一个上楼梯的题目，可以有两种选法： 1.一位数决定一个字母 2.两位数决定一个字母 就相当于dp(i) = dp[i-1] + dp[i-2]; 如果不符合条件，又有两种情况 1.当前数字是0： 不好意思，这阶楼梯不能单独走， dp[i] = dp[i-2] 2.当前数字不是0 不好意思，这阶楼梯太宽，走两步容易扯着步子，只能一个一个走 dp[i] = dp[i-1];
题解
class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == '0':
            return 0
        s = '#' + s
        dp = [0 for _ in range(len(s))]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, len(dp)):
            if s[i] == '0' and s[i-1] not in ['1', '2']:
                return 0
            if 9 < int(s[i-1:i+1]) < 27 :
                dp[i] += dp[i-2]
            if s[i] !='0':
                dp[i] +=  dp[i-1] 
        return dp[-1]
class Solution:
    def numDecodings(self, s: str) -> int:
        s = "#" + s
        dp = [0  for _ in range(len(s))]
        dp[0] = 1
        
        for i in range(1, len(s)):
            # 这种 情况 是无法解码的
            if s[i] == "0" and (i == 1 or s[i-1] not in ["1", "2"]):
                return 0

            #  当前字符组成的 
            if 0 < int(s[i]) <= 9:
                dp[i] = dp[i-1]
            # 加上 和前一个字符公共 组成的
            if i > 1 and 10 <= int(s[i-1:i+1]) <= 26:
                dp[i] += dp[i-2]
        
        return dp[-1]