LeetCode 91. 解码方法（中）

如果一个题目的答案，可以从0开始逐步推导到最终结果，
且状态之间存在转移关系，就可以使用动态规划，逐步保存结果，求解最终答案。

题目

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

1
2
3
4
5
6
7
8
'A' -> 1
'B' -> 2
...
'J' -> 10
...
'T' -> 20
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例

示例 1:

1
2
3
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

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

考察知识点

动态规划

核心思想

方法一、动态规划

直觉
设定状态: f[i] 表示字符串前 i 位有多少种解码方案

边界 : dp[0] = dp[1] = 1

状态转移方程:
分三种情况讨论：

  1. 若 s[i-1] 和 s[i] 连起来表示的数字在 10~26 范围内且 s[i-1] != "0"，则状态转移方程为 \(dp[i] = dp[i] + dp[i-1] + dp[i-2]\)，10~26中一般情况。
  2. 若 s[i-1] 和 s[i] 连起来表示的数字在 10~26 范围内且 s[i-1] == "0"，则状态转移方程为 \(dp[i] = dp[i] + dp[i-2]\)，10~26中10和20的特殊情况。
  3. 若字符串中 s[i] 表示的阿拉伯数字在 1~9 范围内, \(dp[i] = dp[i] + dp[i-1]\)。

10~26两位数情况分析

1
2
3
4
5
6
# 10~26中一般情况：可以连接成两个字母，可以表示两种编码方式。
"22" = "2" + "22" = "TV"
"16" = "1" + "16" = "AO"
# 10~26中10和20的特殊情况：无法连接成两个字母，只能表示一种编码方式。
"20" = "20" = "T"
"10" = "10" = "J"

特判:
1.如果字符串以 '0' 开头, 则直接返回0.
2.如果运算中发现 dp[i] == 0, 则说明此处无法解码, 同样直接返回0.

Python版本

  • 方法一动态规划的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    from typing import List

    class Solution:
        def numDecodings(self, s: str) -> int:
            if s == "" or s[0] == "0":  return 0
            dp = [1, 1]  # 第一位和第二位都是1，即dp[0] = dp[1] = 1，前0位字符占位，设置只有1种解码方案，前1位字符只有1种解码方案。
            for i in range(2, len(s) + 1):
                # 若s[i-1]和s[i]连起来表示的数字在 10~26 范围内, dp[i] += (dp[i-1] + dp[i-2])
                if 10 <= int(s[i-2:i]) <= 26 and s[i-1] != "0":
                    dp.append(dp[i-1] + dp[i-2])
                # 特殊处理一下 10 和 20 的情况，dp[i] += dp[i-2]
                elif int(s[i-2:i]) == 10 or int(s[i-2:i]) == 20:
                    dp.append(dp[i-2])
                # 若字符串中 s[i] 表示的阿拉伯数字在 1~9 范围内, f[i] += f[i-1]
                elif s[i-1] != "0":
                    dp.append(dp[i-1])
                else:  # 如果运算中发现 f[i] == 0, 则说明此处无法解码, 同样直接返回0。 
                    return 0

            return dp[len(s)]

Input = ["12",  "226"]
Answer = [2, 3]
if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
    print("-"*50)
    result = solution.numDecodings(Input[i])
    print(result == Answer[i])

参考链接

九章算法