描述

有一种将字母编码成数字的方式：'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];
}