LeetCode 题解工作台
解码方法 II
一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ： 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" 要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如， "11106" 可以映射为： "AAJF" 对应分…
2
题型
3
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution: def numDecodings(self, s: str) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
一条包含字母 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" 不同。
除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。
给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。
由于答案数目可能非常大，返回 109 + 7 的 模 。
示例 1：
输入：s = "*" 输出：9 解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。 可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。 因此，"*" 总共有 9 种解码方法。
示例 2：
输入：s = "1*" 输出：18 解释：这一条编码消息可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条。 每种消息都可以由 2 种方法解码（例如，"11" 可以解码成 "AA" 或 "K"）。 因此，"1*" 共有 9 * 2 = 18 种解码方法。
示例 3：
输入：s = "2*" 输出：15 解释：这一条编码消息可以表示 "21"、"22"、"23"、"24"、"25"、"26"、"27"、"28" 或 "29" 中的任意一条。 "21"、"22"、"23"、"24"、"25" 和 "26" 由 2 种解码方法，但 "27"、"28" 和 "29" 仅有 1 种解码方法。 因此，"2*" 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。
提示：
1 <= s.length <= 105s[i]是0 - 9中的一位数字或字符'*'
解题思路
方法一
class Solution:
def numDecodings(self, s: str) -> int:
mod = int(1e9 + 7)
n = len(s)
# dp[i - 2], dp[i - 1], dp[i]
a, b, c = 0, 1, 0
for i in range(1, n + 1):
# 1 digit
if s[i - 1] == "*":
c = 9 * b % mod
elif s[i - 1] != "0":
c = b
else:
c = 0
# 2 digits
if i > 1:
if s[i - 2] == "*" and s[i - 1] == "*":
c = (c + 15 * a) % mod
elif s[i - 2] == "*":
if s[i - 1] > "6":
c = (c + a) % mod
else:
c = (c + 2 * a) % mod
elif s[i - 1] == "*":
if s[i - 2] == "1":
c = (c + 9 * a) % mod
elif s[i - 2] == "2":
c = (c + 6 * a) % mod
elif (
s[i - 2] != "0"
and (ord(s[i - 2]) - ord("0")) * 10 + ord(s[i - 1]) - ord("0") <= 26
):
c = (c + a) % mod
a, b = b, c
return c
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should show understanding of dynamic programming and state transition techniques.
- question_mark
Look for clarity in handling wildcard transitions and edge cases, especially leading zeros or invalid combinations.
- question_mark
Check if the candidate understands modular arithmetic to manage large numbers during the computation.
常见陷阱
外企场景- error
Misinterpreting the behavior of the '*' character and failing to count all valid digit possibilities.
- error
Forgetting to handle the modulo operation, potentially causing overflow errors or incorrect results.
- error
Confusing valid two-character decodings, especially when handling transitions between digits.
进阶变体
外企场景- arrow_right_alt
What if the string only contains digits (no '*')? This simplifies the problem to a straightforward dynamic programming approach without the need for wildcard handling.
- arrow_right_alt
What if the input string is extremely large (up to 10^5)? The solution should be optimized to handle such large inputs efficiently using dynamic programming.
- arrow_right_alt
What if the '*' wildcard can also represent '0'? This would change the valid range and require additional checks for validity during decoding.