描述
有一种将字母编码成数字的方式:’a’->1, ‘b->2’, … , ‘z->26’。
现在给一串数字,返回有多少种可能的译码结果
数据范围: 字符串 长度满足 0 < n \le 900< n ≤90
进阶:空间复杂度 O(n) O ( n ),时间复杂度 O(n) O ( n )
示例1
输入:”12″
返回值:2
说明:2种可能的译码结果(”ab” 或”l”)
示例2
输入:”31717126241541717″
返回值:192
说明:192种可能的译码结果
第一种方式
采用递归来解决,把所有按单个字母的结果统计出来 然后再统计两个字符符合条件的结果,两者相加即可,代码如下
public int firstSolve(String nums) {
// write code here
if(nums == null || nums.length() <1){
return 0;
}
char[] chars = nums.toCharArray();
return hanle(chars,0);
}
private int hanle(char[] chars,int index){
if(index == chars.length){
return 1;
}
if(chars[index] == '0'){
return 0;
}
int res1 = hanle(chars,index + 1);
int res2 = 0;
if(index+1 < chars.length && (chars[index] == '1' || (chars[index] == '2' && chars[index+1] <= '6'))){
res2 = hanle(chars,index+2);
}
return res1 + res2;
}
第二种方式
可以采用动态规划来解决, dp [i] 表示字符串nums中以i个位置结尾的前缀字符串的解码种数例如 nums = “123”, 此时dp[0]=1,dp[1]=2,dp[2]=3,当前字符不等于0的时候,dp[i] = dp[i-1],此时将当前位置的一个字符译码当前字符+前一个字符,记为num, 如果 10<=num<=26 此时符合两个合并一起译码的条件;若此时i等于1,直接dp[i]++; 大于1, 则dp[i] += dp[i-2];举个例子: nums = “324” 此时dp[0] = 1, dp[1]呢? dp[2]呢? 很明显nums[1] != ‘0’,所以dp[1] = dp[0],num = 32,此时不满足两个一起译码的条件则循环往下执行,此时 nums[2] != ‘0’,则 dp[2] = dp[1] = 1, num = 24,此时满足两个一起译码的条件,因为i==2大于1,所以dp[2] += dp[2-2] ,dp[2] = 1+1 = 2。代码如下
public int secondSolve (String nums) {
// write code here
if(nums == null || nums.length() <1 || nums.charAt(0) == '0'){
return 0;
}
int[] dp = new int[nums.length()];
dp[0] = 1;
for (int i = 1; i < nums.length(); i++) {
if(nums.charAt(i) != '0'){
dp[i] = dp[i-1];
}
if((nums.charAt(i-1) == '1') || (nums.charAt(i-1) == '2' && nums.charAt(i) <= '6' )){
if(i == 1){
dp[i] +=1;
}else {
dp[i] += dp[i-2];
}
}
}
return dp[nums.length() - 1];
}