把数字翻译成字符串

和之前爬楼梯的题目类似。区别在于：

1. 如果当前字符为0，那它就不是一个合法的解析；
2. 当解析相邻2位时：第一位为0，则与上面的情况类似，不重复累加；第一位为1，则第二位为0~9；第一位为2，则第二位为0~6；其他情况不合法

import java.util.*;


public class Solution {
    public int solve (String nums) {
        int n = nums.length();
        if (n == 0) return 0;

        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] += nums.charAt(0) == '0' ? 0 : dp[0];

        for (int i = 2; i <= n; i++) {
            dp[i] += (nums.charAt(i-1) == '0' ? 0 : dp[i-1]);
            dp[i] += (verifyTwoChar(nums.charAt(i-2), nums.charAt((i-1))) ? dp[i-2] : 0);
        }

        return dp[n];
    }

    private boolean verifyTwoChar(char ch1, char ch2) {
        switch (ch1) {
            case '1': return ch2 >= '0' && ch2 <= '9'; 
            case '2': return ch2 >= '0' && ch2 <= '6';
            default: return false;
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here

        // 算法核心思想：从0到n，以n为出口的记忆化搜索

        // dp[i] - 表示从第i字符到结尾，总共有dp[i]种译法
        int[] dp = new int[nums.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }


        return process(nums, 0, dp);
    }

    public int process (String nums, int i, int[] dp) {
        int n = nums.length();
        // 递归出口
        if (i == n) {
            dp[i] = 1;
            return dp[i];
        }

        // 递归分支
        if (dp[i] != -1) {
            return dp[i];
        }
        // 可以只译当前一位数，也可以尝试译两位数

        // 先尝试只译一位数
        int num = Integer.parseInt(nums.substring(i, i + 1));
        int one = 0;
        if (num != 0) {
            // 注意非0
            if (dp[i + 1] == -1) {
                dp[i + 1] = process(nums, i + 1, dp);
            }
            one = dp[i + 1];
        }

        // 再尝试译两位数
        int two = 0;
        if (i < n - 1 && num != 0) {
            // 确保不越界，且不以0开头
            num = Integer.parseInt(nums.substring(i, i + 2));
            if (num > 0 && num <= 26) {
                // 合法字母
                if (dp[i + 2] == -1) {
                    dp[i + 2] = process(nums, i + 2, dp);
                }
                two = dp[i + 2];
            }
        }

        // 计算结果
        dp[i] = one + two;
        return dp[i];
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        int n = nums.length();
        if (n <= 1) {
            return nums.charAt(0) - '0' > 0 ? 1 : 0;
        }
        int[] dp =  new int[n];
        dp[0] = nums.charAt(0) - '0' > 0 ? 1 : 0;
        dp[1] = nums.charAt(1) - '0' > 0 ? dp[0] * 1 : 0;
        int num = Integer.parseInt(nums.substring(0, 2));
        if (num > 0 && num <= 26) {
            dp[1] += 1;
        }

        for (int i = 2; i < n; i++) {
            int val1 = nums.charAt(i) - '0';
            dp[i] = val1 > 0 ? dp[i - 1] * 1 : 0;
            int val2 = Integer.parseInt(nums.substring(i - 1, i + 1));
            if (val2 >= 10 && val2 <= 26) {
                dp[i] += dp[i - 2] * 1;
            }
        }
        return dp[n - 1];
    }
}

动态规划解该题，发现有点小坑，开始我一直纠结110，110110这种不应该都是1吗，结果官方题解是2和4

结果发现，动态规划应该考虑3种情况：

• 前两个数是10和20：dp[i] = dp[i-2];
• 考虑可以组合译码，11~26：dp[i] = dp[i-1] + dp[i-2];;
• 其他情况只有一种方式，直接译码：dp[i] = dp[i-1];

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here
        if(nums.equals("0")) return 0;
        if(nums.equals("10") || nums.equals("20")) return 1;

        for(int i = 1; i<nums.length(); i++)
            if(nums.charAt(i) == '0' && nums.charAt(i-1) != '1' && nums.charAt(i-1) != '2')
                return 0;

        int[] dp = new int[nums.length() + 1];
        Arrays.fill(dp, 1);

        for(int i=2; i<=nums.length(); i++){
            // 考虑10和20的情况
            if(nums.charAt(i-1) == '0' && (nums.charAt(i-2) == '1' || nums.charAt(i-2) == '2')){
                dp[i] = dp[i-2];
            }
            // 考虑组合译码的情况（非10和20）
            else if(nums.charAt(i-2) == '1' && nums.charAt(i-1) != '0' ||
             nums.charAt(i-2) == '2' && nums.charAt(i-1) > '0' && nums.charAt(i-1) < '7'){
                dp[i] = dp[i-1] + dp[i-2];
            }
            // 直接译码
            else{
                dp[i] = dp[i-1];
            }
        }
        return dp[nums.length()];
    }
}

import java.util.*;


public class Solution {
    public int solve (String nums) {
        int[] dp = new int[nums.length() + 1];
        if (nums.equals("0")) return 0;
        //初始化dp
        dp[0] = 1;
        dp[1] = 1;
        //中间部分
        for (int i = 2; i < dp.length; i++) {
            String str = "" + nums.charAt(i - 2) + nums.charAt(i - 1);
            if (nums.charAt(i - 1) == '0' && (nums.charAt(i - 2) != '1' &&
                                              nums.charAt(i - 2) != '2')) {
                return 0;
            }
            if (str == "00") {
                return 0;
            }
            if (str.equals("10") || str.equals("20") || (nums.charAt(i - 2) == '2' &&
                    nums.charAt(i - 1) > '6') || nums.charAt(i - 2) > '2' ||
                    nums.charAt(i - 2) == '0') {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = dp[i - 2] + dp[i - 1];
            }

        }
        return dp[dp.length - 1];
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here
        // dp[i]，分割点在i时返回可能的编码结果数
        // 假设分割点在i， dfs(i) = dfs(i - 2)[在i - 2和 i - 1合法时] + dfs(i - 1)
        //排除0
        if(nums.equals("0")) 
            return 0;
        int len = nums.length();
        System.out.print(len);
        int[] dp = new int[len + 1];
        dp[1] = 1;
        dp[0] = 1;
        for(int i = 2; i <= len; i++) {
            int left = 0;
            int right = 0;
            if(judge(nums.substring(i - 2, i))) left = dp[i - 2];
            if(nums.charAt(i - 1) != '0') right = dp[i - 1];
            dp[i] = left + right;
        }
        return dp[len];
    }

    private boolean judge(String s) {
        if(s.charAt(0) == '0') return false;
        return Integer.valueOf(s) <= 26? true : false; 
    }
}

public class Solution {
    public int solve (String nums) {
        if(nums.charAt(0) == '0') return 0;
        int matrix[] = new int[nums.length()];
        matrix[0] = 1;
        for(int i = 1; i < nums.length(); i++) {
            int value = i == 1 ? 1 : matrix[i-2];
            matrix[i] = (nums.charAt(i) == '0' ? 0 : matrix[i-1]) + ( Integer.parseInt(nums.substring(i-1, i+1)) >= 10 && Integer.parseInt(nums.substring(i-1, i+1)) < 27 ? value : 0);
            if(matrix[i] == 0) return 0;
        }
        return matrix[nums.length()-1];
    }
}

import java.util.*;


public class Solution {
    /**
        本质是爬楼梯，你想想当前层有多少种到达可能。无非就是看看i-1和i-2这两条路径中，哪一条可行。
     */
    public int solve (String nums) {
        // write code here
        //dp多一位
        int[] dp = new int[nums.length()+1];
        dp[0] = 0;
        //处理不同的初始情况，首位为0，则到达位置1的可能为0种，否则为1；
        if(nums.charAt(0) == '0'){
            dp[1] = 0;
        }else{
            dp[1] = 1;
        }
        //下面类似爬楼梯数爬法，到达当前的可能性，无法就是i-1和i-2这两种情况，哪条路径走得通。
        for(int i = 2; i <= nums.length(); i++){
            int method1= 0;
            int method2= 0;
            //i-1这条路径
            if(nums.charAt(i-1) != '0'){
                method1 = dp[i-1];
            }
            //i-2这条路径
            if(nums.charAt(i-2)>'0' && nums.charAt(i-2)<='1' 
                || nums.charAt(i-2)>'1' && nums.charAt(i-2)<='2' && nums.charAt(i-1)<='6'){
                //由于dp[0]=0, 当测试用例为"10"时，其实method为1。
                method2 = dp[i-2] == 0 ? 1 : dp[i-2];
            }

            dp[i] = method1 + method2;            
        }
        return dp[nums.length()];
    }
}

public int solve (String nums) {
        // 1-9  只有一种译码    11-19、21-26  两种译码  (除去10、20)
        //dp[i]，前i个数的译码方法有多少种
        //两种译码：直接译码(dp[i]=dp[i-1])和组合译码(dp[i]=dp[i-2])  所以dp[i]=dp[i-1]+dp[i-2]
        //一种译码：直接译码(dp[i]=dp[i-1])  所以dp[i]=dp[i-1]
        //依次相加，dp[length]
        if(nums.equals("0")) return 0;
        if(nums=="10"||nums=="20") return 1;
        //当0前面，不是1不是2，无法译码，0种   不是10、不是20  则无法译码
        for(int i=1;i<nums.length();i++){
            if(nums.charAt(i)=='0'){
                if(nums.charAt(i-1)!='1'&&nums.charAt(i-1)!='2'){
                    return 0;
                }
            }
        }
        //
        int[] dp=new int[nums.length()+1];
        Arrays.fill(dp,1);//初始化为1，有1种译码方式
        for(int i=2;i<nums.length()+1;i++){
            //11-19 21-26
            if(((nums.charAt(i-2)=='1'&&nums.charAt(i-1)!='0')||(nums.charAt(i-2)=='2'&&nums.charAt(i-1)<'7'&& nums.charAt(i-1)>'0'))){
                dp[i]=dp[i-1]+dp[i-2];
            }else{
                dp[i]=dp[i-1];
            }
        }
        return dp[nums.length()];
 
    }

public class Solution {
    public int solve (String nums) {
        // nums[0,i-1]可以翻译成dp[i]种字符串
        int[] dp = new int[nums.length()];
        dp[0] = nums.charAt(0) == '0' ? 0 : 1;
        for (int i = 1; i < dp.length; i++) {
            if (nums.charAt(i) != '0') {
                dp[i] = dp[i - 1];
            }
            if (isValid(nums.charAt(i - 1), nums.charAt(i))) {
                if (i - 2 >= 0) {
                    dp[i] += dp[i - 2];
                } else {
                    dp[i]++;
                }
            }
        }
        return dp[nums.length() - 1];
    }
    private boolean isValid(char c1, char c2) {
        if (c1 == '0' || c1 >= '3') {
            return false;
        }
        if (c1 == '1') {
            return c2 >= '0' && c2 <= '9';
        }
        return c2 >= '0' && c2 <= '6';
    }
}

    public int solve (String nums) {
        int pre1 = 1, pre2 = 0;
        char[] cs = nums.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            int t = pre1, cont = i == 0 ? 0 : (cs[i - 1] - '0') * 10 + cs[i] - '0';
            if (cs[i] == '0') pre1 = 0;
            if (i != 0 && cont <= 26 && cont >= 10) pre1 += pre2;
            pre2 = t;
        }
        return pre1;
    }