这个题的边界条件很不好搞, WA 了好多次
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function (s) {
const h = function (n) {
const r = [0, 1, 2];
if (parseInt(s[0] + s[1]) > 26) r[2] = 1;
if (parseInt(s[0] + s[1]) === 10 || parseInt(s[0] + s[1]) === 20) { r[1] = 1; r[2] = 1; }
if(parseInt(s[0]) > 2 && s[1] === '0') return 0;
for (let i = 3; i <= n; i++) {
if(parseInt(s[i - 2]) > 2 && s[i - 1] === '0') return 0;
r[i] = (parseInt(s[i - 1]) > 0 ? r[i - 1] : 0) + (parseInt(s[i - 2] + s[i - 1]) > 9 && parseInt(s[i - 2] + s[i - 1]) < 27 ? r[i - 2] : 0);
}
return r[n];
}
if (s[0] === '0') return 0;
return h(s.length);
};
简介优雅的解法
public class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n == 0) return 0;
int[] memo = new int[n+1];
memo[n] = 1;
memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;
for (int i = n - 2; i >= 0; i--)
if (s.charAt(i) == '0') continue;
else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];
return memo[0];
}
}