面试题46：把数字翻译成字符串

• 给定一个数字，我们按照如下的规则把它翻译成字符串

0 -> a
1 -> b
2 -> c
...
25 -> z

一个数字可能有多种翻译，比如12258有五种，分别是"bccfi", "bwfi","bczi","mcfi", "mzi".
请实现一个函数，用来计算一个数字有多少种不同的翻译方法。

思路一：
采用递归的思路，对于每个字符串采用同样的编辑方式。只取一个字符串，或者只取两个字符串，分别递归剩下的字符串，并进行回溯，即删掉最后的字符。递归结束的方式是采用传入的字符被取空，并将构造的sb添加进入list。

注意：两位数需要检查是否在10到25之间。映射字符时只需要将当前字符转化为数字，加上97，转换为字符，即对应的字母。

/**
     * 从左到右的递归
     * @param n
     * @return
     */
    public List<String> translateNum(int n) {
        List<String> list = new ArrayList<>();
        if (n < 0) return list;

        String numString = String.valueOf(n);
        StringBuilder sb = new StringBuilder();
        translateToLetter(sb, list, numString.trim());
        return list;
    }

    private void translateToLetter(StringBuilder sb, List<String> list, String numString) {
        //字符被取空，跳出
        if (numString.equals("") || numString.isEmpty()){
            list.add(sb.toString());
            return;
        }
        //只取一位
        String s1 = numString.substring(0,1);
        char c1 = numToLetter(s1);
        sb.append(c1);
        translateToLetter(sb, list, numString.substring(1));
        //替换最后一位考虑其他情况
        sb.deleteCharAt(sb.length()-1);

        //取两位，保证位数大于1
        if (numString.length() > 1){
            String s2 = numString.substring(0,2);

            if (check(s2)){
                char c2 = numToLetter(s2);
                sb.append(c2);
                translateToLetter(sb, list, numString.substring(2));
                //替换最后一位
                sb.deleteCharAt(sb.length() - 1);
            }
        }

    }
    /**
     * 当一次翻译两位数时，检查是否范围在10-25之间
     */
    private boolean check(String s) {
        int x = Integer.parseInt(s);
        return  x >= 10 && x <= 25;
    }
    /**
     * 数字 -> 字母的映射，a的ASCII码是97，所以0-25的数字加上97就得到了题目中的映射
     */
    private char numToLetter(String s) {
        return (char) (Integer.parseInt(s) + 97);
    }

思路二：
从后向前，运用的递归，新建一个数组，从后往前记录各个位置的可能性，初始化最后一位为1。从倒数第二位开始循环，如果和后一位数字字符能构成符合条件的两位数，则有两种情况，一个是不存在后一位的下一位，即倒数第二位，则加1，如果存在则加上后面两位对应的数值。
另外如果两位符合条件，则直接赋前面的值。
代码如下：

/**
     * 从右到左直接计数
     */
    public int getTranslateCount(int n) {
        if (n < 0) return -1;
        return Count(String.valueOf(n));
    }

    private int Count(String number) {
        int len = number.length();
        int[] count = new int[len];
        count[len-1] = 1;
        for (int i=len-2;i>=0;i--){
            int high = number.charAt(i) - '0';
            int low = number.charAt(i+1) - '0';
            int combineNum = high*10 + low;
            //联合值必须在10-25之间才满足条件
            if (combineNum >= 10 && combineNum <= 25){
                //当前索引在倒数第二位，不存在i+2，只可能多增加一种翻译的方法
                if (i == len-2) count[i] = count[i+1] + 1;
                //当前索引存在i+2，则可以通过前一个字母到达当前，或者前两个字母联合到达当前，循环往复
                else count[i] = count[i+1] + count[i+2];
            }else {
                count[i] = count[i+1];
            }
        }
        //返回从首字母开始的计数
        return count[0];
    }