题目
题目链接
题解
class Solution {
public int numDecodings(String s) {
if (s.charAt(0) == '0') {
return 0;
}
int len = s.length();
int[] dp = new int[len];
dp[0] = 1;
/*
* 转移方程
* 单独 int solo = dp[i - 1], s[i] != 0
* 0, s[i] == 0
* 组合 int comb = dp[i - 2], s[i - 1] != 0 && i >= 2 && (s[i - 1] - '0') * 10 + (s[i] - '0') <= 26
* 1, s[i - 1] != 0 && 0 <= i < 2 && (s[i - 1] - '0') * 10 + (s[i] - '0') <= 26
* 0, other
* dp[i] = solo + comb
*/
for (int i = 1; i < len; i++) {
if (i - 1 >= 0 ) {
// 单独编码
int solo = 0;
if (s.charAt(i) != '0') {
solo = dp[i - 1];
}
// 组合编码
int comb = 0;
if (s.charAt(i - 1) != '0') {
if ((s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0') <= 26) {
if (i - 2 >= 0) {
comb = dp[i - 2];
} else {
comb = 1;
}
}
}
dp[i] = solo + comb;
}
}
return dp[len - 1];
}
}