题意:给定一个字符串,里边是0-9的字符,数字的组合解码成a-z,求它的所有解码组合
思路:设一个dp数组,来记录当前index的组合数,设一个pre来记录上一个遍历到的数
- 当当前数是0,如果上一个数不是1和2,那么数组违法,返回0,否则dp[i] = dp[i-2],因为i-1和i只能和在一起组成“10”或“20”
- 当pre是1时,那么dp[i] = dp[i-1]+dp[i-2],因为当前数即可以自己算一个字符,也可以和1一起组成一个字符
- 当pre时2时,
如果cur是1-6,那么dp[i] = dp[i-1]+dp[i-2],因为当前数即可以自己算一个字符,也可以和1一起组成一个字符
否则 dp[i] = dp[i-1],因为当前数只能自己算一个字符 - 对于其他情况dp[i] = dp[i-1],因为当前数只能自己算一个字符
思想:动态规划
复杂度:时间O(n),空间O(n)
class Solution {
public int numDecodings(String s) {
int len = s.length();
if(len == 0)
return 0;
int[] dp = new int[len+1];
int pre = 0;
dp[0] = 1;
for(int i=1;i<=len;i++) {
int cur = s.charAt(i-1) - '0';
if(cur == 0) {
if(pre != 1 && pre != 2) {
return 0;
}
dp[i] = dp[i-2];
} else if(pre == 1) {
dp[i] = dp[i-1] + dp[i-2];
} else if(pre == 2) {
if(cur>=1&&cur<=6)
dp[i] = dp[i-1] + dp[i-2];
else
dp[i] = dp[i-1];
} else {
dp[i] = dp[i-1];
}
pre = cur;
}
return dp[len];
}
}
网友评论