LeetCode 91. 解码方法
目录
题目描述
✅ 91. 解码方法
题意分析
编码规则是
A对应1、B对应2，一直到Z对应26。现在给一个只含数字的字符串，问把它按这套规则反过来解码，一共有多少种不同的方案。注意题目只要方案数这一个整数，既不要求列出所有方案，也不要求给出字典序最小的那一种——这决定了我们不必真的做搜索，只需要计数。关键约束在于编码表里没有
0。这带来两条彼此独立的限制。第一，字符'0'永远不能单独成为一个字母，任何时候把一个'0'当作独立单元切出来都是非法的。第二，两位组合不允许有前导零，因为06和6在编码表里不是同一件事，编码F时写下的一定是6而不是06，所以"06"的方案数是0而不是1。很多人只记住了「两位要在 10 到 26 之间」这半句，其实下界10正是在排除前导零。由此可以把合法的切分单元收敛成两类：一个字符，且它不是
'0'；或者两个字符，且它们组成的数落在10到26的闭区间内。整个串必须被这些单元不重不漏地铺满，铺法的数量就是答案。边界方面：字符串非空，长度可达上百，方案数题目保证在 32 位整数范围内。首字符如果是
'0'，那它既不能单独解码、又没有前一位可以合并，直接判定为0种方案。串中出现"00"、或者出现一个前面数字大于2的'0'（比如"30"），同样会让方案数归零。这些情况不需要逐个特判，只要转移写对，0会自然地被算出来并顺着递推传下去。
解法：滚动动态规划统计解码数
核心思路
问题关键：每个字母只可能由 1 位或 2 位数字解码；
0不能单独解码，两位数只有10..26合法。暴力递归会在每个位置反复计算相同后缀，最坏呈指数增长。为什么选动态规划：一个前缀的方案数只取决于它去掉最后 1 位或 2 位后的方案数。定义
dp[i]为前i个字符的解码方案数，dp[0] = 1表示“空前缀有一种不做任何事的方案”，使整段两位数也能从统一公式转移。对前缀末尾分类：
- 若
s[i - 1] != '0'，末位可单独解码，贡献dp[i - 1]；- 若末两位数在
10..26，它们可合并解码，贡献dp[i - 2]。两类按“最后一个编码单元的长度”划分，互斥且覆盖所有合法解码，因此贡献直接相加。又因为
dp[i]只依赖前两项，用pre2、pre1滚动即可。正确性：任意完整方案的最后一个单元必为合法的 1 位或 2 位编码，删除它后分别唯一对应一个
dp[i - 1]或dp[i - 2]的方案；反过来，在这些方案末尾接上合法单元仍是合法且不会重复。由此转移精确计数全部方案。
解题步骤
- 首字符为
0时直接返回0；它既不能单独解码，也没有前一位可合并。- 初始化
pre2 = dp[0] = 1、pre1 = dp[1] = 1。- 从第二个字符开始遍历：先令
cur = 0，末位非0时加pre1，末两位在10..26时加pre2。- 按
pre2 = pre1、pre1 = cur的顺序滚动，最后返回pre1。面试口述示例：
226中，dp[2] = dp[1] + dp[0] = 2（2|2、22）；到6时，单独解码贡献 2，26合并再贡献 1，所以答案为 3。边界反例：
06因首位为零返回 0；10只有整体解码这一种；100在最后一个0处既不能单独取，00也不合法，方案数自然降为 0。
代码实现
class Solution {
public int numDecodings(String s) {
if (s.charAt(0) == '0') {
return 0;
}
int pre2 = 1;
int pre1 = 1;
for (int i = 1; i < s.length(); i++) {
int cur = 0;
if (s.charAt(i) != '0') {
cur += pre1;
}
int twoDigits = (s.charAt(i - 1) - '0') * 10
+ s.charAt(i) - '0';
if (twoDigits >= 10 && twoDigits <= 26) {
cur += pre2;
}
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}
func numDecodings(s string) int {
if s[0] == '0' {
return 0
}
pre2, pre1 := 1, 1
for i := 1; i < len(s); i++ {
cur := 0
if s[i] != '0' {
cur += pre1
}
twoDigits := int(s[i-1]-'0')*10 + int(s[i]-'0')
if twoDigits >= 10 && twoDigits <= 26 {
cur += pre2
}
pre2, pre1 = pre1, cur
}
return pre1
}
复杂度分析
- 时间复杂度：$O(n)$，只从左到右扫描一次字符串，每个位置做常数次判断和加法。
- 空间复杂度：$O(1)$，只保存相邻两个 DP 状态和当前值。
关键点总结
- 计数型 DP 可以按“最后一步”划分方案；本题只需枚举末尾取 1 位还是 2 位。
dp[0] = 1是空前缀的计数单位，不代表空字符串有一个字母；它保证12整体解码时能贡献一种方案。0的约束应放进转移：单字符必须非零，两字符必须位于10..26。- 两条转移可能同时成立，必须相加而不是写成
if / else if；滚动变量则要保留更新前的两项。
易错点总结
- 无条件加入单字符分支：
106会把0单独解码，错算出额外方案。- 两位数只检查
<= 26：会把带前导零的06当成合法编码，必须同时检查>= 10。- 把
dp[0]设为 0：12会漏掉整体解码成L的方案。- 两条合法分支写成
else if：11只能计入1|1或11之一，答案从 2 错成 1。- 滚动时先覆盖
pre1再保存旧值：后续转移会读取到同一项，破坏dp[i-2]、dp[i-1]的含义。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 剑指 Offer 46. 把数字翻译成字符串 | 中等 | 同型转移但区间是 10 到 25，且输入是整数需先逐位拆解 |
| 70. 爬楼梯 | 简单 | 剥去合法性判断后的裸骨架，两支转移永远成立 |
| 509. 斐波那契数 | 简单 | 同样的两项递推，用来练滚动变量与边界项的含义 |
| 198. 打家劫舍 | 中等 | 转移同样看「最后一步选一格还是两格」，但目标从计数变最值 |
| 1155. 掷骰子等于目标和的方法数 | 中等 | 计数 DP 的多分支版本，末位枚举从 2 支扩到 k 支且需取模 |