91. 解码方法
题目描述
字母 A 到 Z 依次编码为数字 1 到 26。一条大写字母消息编码后，就得到一个数字串。
输入非空数字串 s。解码时把 s 切成若干段，每段必须是 1 到 26 之间的数，且不能带前导零，比如 "06" 不是合法的一段。例如 "11106" 可切成 (1,1,10,6) 或 (11,10,6)。
返回把整个 s 切成合法各段的方法数。没有任何合法切法时返回 0。保证答案在 32 位整数范围内。
示例 1
输入：s = "12" 输出：2
解释：可以是 1 2（AB）或 12（L）。
示例 2
输入：s = "226" 输出：3
解释：可以是 2 26、22 6、2 2 6。
示例 3
输入：s = "06" 输出：0
解释：开头的 0 无法单独成段，06 又有前导零，所以无法解码。
数据范围
1 <= s.length <= 100s只含数字，开头可能是0。
解题思路
设 dp[i] 为前 i 个字符的解码方法数，dp[0] = 1 表示空前缀有一种解法。看最后一段：如果 s[i-1] 不是 0，它可以单独成一段，加上 dp[i-1]；如果最后两位 s[i-2..i-1] 在 10–26 之间，它们可以合成一段，加上 dp[i-2]。
为什么正确
dp[i] 只依赖 dp[i-1] 和 dp[i-2]，从左到右依次计算。
复杂度分析
时间 O(n)，空间 O(n)（可以压缩到 O(1)）。
易错点
0 不能单独解码，只能作为 10 或 20 的一部分；两位数以 0 开头（如 '06'）也不合法。用字符串比较 '10' <= x <= '26' 可以自动排除前导 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
if s[i - 1] != '0':
dp[i] += dp[i - 1]
if i >= 2 and '10' <= s[i - 2:i] <= '26':
dp[i] += dp[i - 2]
return dp[n]class Solution {
public int numDecodings(String s) {
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (s.charAt(i - 1) != '0') {
dp[i] += dp[i - 1];
}
if (i >= 2 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
}class Solution {
public:
int numDecodings(string s) {
int n = s.size();
vector<long long> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (s[i - 1] != '0') {
dp[i] += dp[i - 1];
}
if (i >= 2 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
dp[i] += dp[i - 2];
}
}
return (int)dp[n];
}
};func numDecodings(s string) int {
n := len(s)
dp := make([]int, n+1)
dp[0] = 1
for i := 1; i <= n; i++ {
if s[i-1] != '0' {
dp[i] += dp[i-1]
}
if i >= 2 && (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) {
dp[i] += dp[i-2]
}
}
return dp[n]
}var numDecodings = function(s) {
const n = s.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= n; i++) {
if (s[i - 1] !== '0') {
dp[i] += dp[i - 1];
}
if (i >= 2 && (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6'))) {
dp[i] += dp[i - 2];
}
}
return dp[n];
};function numDecodings(s: string): number {
const n = s.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= n; i++) {
if (s[i - 1] !== '0') {
dp[i] += dp[i - 1];
}
if (i >= 2 && (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6'))) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}