91. 解码方法（Decode Ways）
频次 ★★★ · 难度 🟡 · 高频：字节/美团
题目
给定一串数字字符串 s（只含 ‘1’-‘9’ 和 ‘0’），按照 A→1, B→2, ..., Z→26 的映射进行解码，求有多少种解码方式。
示例：
输入: s = "226"
输出: 3 （"BZ"(2,26), "VF"(22,6), "BBF"(2,2,6)）
输入: s = "06"
输出: 0 （"06" 不能当作 "6" 解码，前导零无效）
思路
一维 DP：dp[i] 表示 s 的前 i 个字符（s[0..i-1]）的解码方式数。
- 单字符解码：若
s[i-1] ≠ '0'，则dp[i] += dp[i-1] - 双字符解码：若
s[i-2..i-1]在"10"到"26"之间，则dp[i] += dp[i-2]
初始化 dp[0] = 1（空串算一种方式），dp[1] = s[0] != '0' ? 1 : 0。
空间优化：滚动两个变量代替数组。
代码
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0')
return 0;
int prev2 = 1; // dp[i-2]
int prev1 = 1; // dp[i-1]
for (int i = 1; i < s.length(); i++) {
int cur = 0;
// 单字符
if (s.charAt(i) != '0')
cur += prev1;
// 双字符
int two = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
if (two >= 10 && two <= 26)
cur += prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}复杂度
- 时间：O(n) —— 一次遍历
- 空间：O(1)
边界条件
- 空串或首字符为 ‘0’：直接返回 0
- 字符串含连续零（如 “100”）：
s[1..2]="00"既不能单字符解码（0 ≠ valid），也不能双字符解码（00 不在 10-26），cur 为 0，后续全为 0 - 单个字符且不为 ‘0’：返回 1
变式
- 剑指 Offer 46. 把数字翻译成字符串：0-25 映射，本质相同但 0 可单独映射，且无前导零限制
- 含 ’*’ 通配符的解码（LeetCode 91 的扩展）：’*’ 可以代表 1-9，分类讨论更复杂
- 优化空间：上面代码已优化为 O(1)
易错点
- ‘0’ 不能单独解码，但可以和前一个 ‘1’ 或 ‘2’ 组成 “10” 或 “20”；单独的 ‘0’ 和 “00”、“30” 等都无法解码
dp[0] = 1是递推基础（空串有一种解码方式），不是实际含义，需要理解清楚- 计算双字符时注意
two >= 10的判断——这隐含了不能有前导零（“06” → two=6 < 10，不计入）
面试追问
- 如果数字非常大怎么办？ 答案可能溢出 int，用 long 或取模 10^9+7；斐波那契式增长，n=100 时答案接近 10
- 字符串里面包含 * 呢？ 状态转移更复杂：'' = 1-9 共 9 种可能，双字符时 '' 与 ‘0’-‘9’ 组合要逐情况 ×2 或 ×9 或 ×15 等