解码方法
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
一条包含字母 A-Z 的消息通过以下映射进行了 编码：
"1" → 'A'，"2" → 'B'，…，"25" → 'Y'，"26" → 'Z'。
然而，在 解码 已编码的消息时，有些编码被包含在其它编码当中（如 "2" 与 "5" 也可组成 "25"）。
给你一个只含数字的 非空 字符串 s，请计算并返回 解码 方法的 总数。若无法合法解码整个字符串，返回 0。
题目数据保证答案为 32 位整数。
示例 1
"AB"（1, 2）或 "L"（12）。示例 2
"BZ"（2, 26）、"VF"（22, 6）、"BBF"（2, 2, 6）。示例 3
"06" 不能作为合法两位编码（前导零），整串无法解码。模拟答题者思考
1. 最直接：从左到右 DFS，每位尝试切 1 个或 2 个数字，遇到非法（如前导零、>26）回溯。分支在重叠子问题上爆炸，n=100 会超时。
2. 重复在哪里？「前 i 个字符有多少种解码」只依赖更短前缀的方案数，与具体字母路径无关——同一前缀被不同 DFS 路径反复访问。
3. 关键转化：设 f(i) = s[0..i) 的方案数。最后一刀要么只取 s[i-1]（不能是单独的 '0'），要么取 s[i-2..i) 且数值在 [10,26]（单 digit 的 1–9 走一位分支）。则 f(i) = f(i-1)的合法贡献 + f(i-2)的合法贡献，与 #70 爬楼梯「最后一步 1 或 2」同形，但每步要先判字符是否允许切分。
4. 手推 "226"：f(0)=1；"2"→1；"22" 可 2+2 或 22→2；"226" 末位 6 单独、或 26 一起→3，与样例一致。
5. "06"：首位单独 0 非法，两位 06 也非法，f(1)=0 传导使答案为 0——前导零必须在转移里挡掉，不能当普通一位数字。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dp[i]（或 prev2, prev1） | int | 定义：前缀 s[0..i)（长度为 i）的合法解码方案总数维护： dp[0]=1 表示空前缀一种方式；推到 i 时只看最后一格单独解码或最后两格一起解码更新：若末位单字符合法则 += dp[i-1]；若末两位在 10–26 则 += dp[i-2] |
prev1 | int | 定义：滚动数组中当前的 dp[i-1]（上一前缀的方案数）维护：每处理完位置 i，该值将成为下一轮的「前一项」更新：每轮先保存旧 prev1 到 prev2，再把新算出的 cur 赋给 prev1 |
prev2 | int | 定义：滚动数组中的 dp[i-2]维护：与 prev1 同步前移，供「两位一组」转移使用更新： prev2, prev1 = prev1, cur 式滚动 |
cur | int | 定义：正在计算的 dp[i]维护：每轮从 0 累加：单字符分支 + 双字符分支（各自判合法） 更新：若 cur==0 且已无法延续，可提前结束；最终 prev1 即为 dp[n] |
落码步骤
1. 若 s[0]=='0' 或空串，直接返回 0
2. 初始化 prev2=1（dp[0]）、prev1=1（dp[1] 在首字符非 0 时）
3. 对 i 从 2 到 n，令 cur=0
4. 单字符：若 s[i-1]!='0'，则 cur += prev1
5. 双字符：取 two = int(s[i-2:i])，若 10 <= two <= 26，则 cur += prev2
6. 滚动 prev2, prev1 = prev1, cur；若中途 cur==0 可继续（后面仍可能为 0）
7. 返回 prev1（即 dp[n]）
代码实现
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == "0":
return 0
n = len(s)
prev2, prev1 = 1, 1
for i in range(2, n + 1):
cur = 0
if s[i - 1] != "0":
cur += prev1
two = int(s[i - 2 : i])
if 10 <= two <= 26:
cur += prev2
prev2, prev1 = prev1, cur
return prev1class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s[0] == '0') return 0;
int n = s.size();
long prev2 = 1, prev1 = 1;
for (int i = 2; i <= n; ++i) {
long cur = 0;
if (s[i - 1] != '0') cur += prev1;
int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
if (two >= 10 && two <= 26) cur += prev2;
prev2 = prev1;
prev1 = cur;
}
return (int)prev1;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)（n 为字符串长度，每位至多看一位与两位切分）
O(1)（滚动两个状态；数组版 dp 为 O(n)）
常见坑
忽略前导零：两位编码必须是 10–26；"06"、"01" 不能走双字符分支，且单独的 '0' 不能走单字符分支，否则会把非法串算成有解。
与爬楼梯混淆：不是无脑 dp[i]=dp[i-1]+dp[i-2]，每一位转移前都要判当前切分是否对应 1–26 的合法映射。
初始化 dp[1]：仅当 s[0]!='0' 时为 1；若首字符为 0，整个答案为 0，不要默认 dp[1]=1。
必测边界 Case
s = "12" → 2
s = "06" → 0
s = "10" → 1（只能 10，不能 1+0）
s = "8" → 1
s = "0" → 0