https://leetcode-cn.com/problems/decode-ways-ii/submissions/
这道题先按递归做,发现超时,然后改成用动态规划
事实证明,递归代码容易写,但是效率一般低点
public int numDecodings(String s) {
if(s.length()==0){
return 0;
}else if(s.length()==1){
return (int)getC(s.charAt(0));
}
long[] dp = new long[s.length()];
dp[0] = getC(s.charAt(0));
dp[1] = dp[0] * getC(s.charAt(1)) + getCC(s.charAt(0), s.charAt(1));
for (int i = 2; i < s.length(); i++) {
//只有两个可能,要么一位要么两位
dp[i] = dp[i - 2] * getCC(s.charAt(i - 1), s.charAt(i));
dp[i] += dp[i - 1] * getC(s.charAt(i));
dp[i] = dp[i]%1000000007;
}
return (int) dp[s.length() - 1];
}
private long getCC(char c1, char c2) {
if (c1 == '*') {
if (c2 == '*') {
return 15;
} else {
if (c2 >= '0' && c2 <= '6') {
return 2;
} else {
return 1;
}
}
} else if (c1 == '1') {
if (c2 == '*') {
return 9;
} else {
return 1;
}
} else if (c1 == '2') {
if (c2 == '*') {
return 6;
} else if (c2 >= '0' && c2 <= '6') {
return 1;
}
}
return 0;
}
private long getC(char c) {
if (c == '*') {
return 9;
} else if (c == '0') {
return 0;
}
return 1;
}
如果有leetcode不明白的题目,欢迎评论,一起探讨