剑指Offer第46题——把数字翻译成字符串

给定一个数字，我们按照如下的规则把它翻译成字符串
0 -> a
1 -> b
2 -> c
...
25 -> z
一个数字可能有多种翻译，比如12258有五种，分别是"bccfi", "bwfi","bczi","mcfi", "mzi".请实现一个函数，用来计算一个数字有多少种不同的翻译方法。

举个简单的例子，比如258，我们可以先翻译第一个数字，得到c，也可以翻译前两个数字，得到z；如果先翻译了一个数，对于剩下的58，和上面一样可以选择只翻译一位，得到f，也可以翻译两位（在这个例子中是不合法的，58没有与之映射的字符），如果先翻译了两位，对于剩下的8，只能有一种翻译方法了，得到i。所以最后得到两种翻译方法，cfi和zi。

从这个简单的例子可以得到一般性的结论，令f(i)为从第i位开始的不同翻译的数目，因为每次可以选择值翻译一个数字，也可一次翻译两个数字，而对于剩下的数字也可以采用同样的方法，这是一个递归问题。

其中表示从第i位数字开始的不同翻译的数目。其中n为数字的位数，可取0或者1，当一次翻译两个数字时，如果这个数字在的范围内，这就是一个可翻译的数，此时为1，否则为0。根据题意，我们最后就是要求得

但是对于从左往右的递归，可能会出现重复的计算，可以使用从右往左的递归
对于上面的公式，也就是先求出，然后求出，之后根据这两个值求出，然后根据和求出一直往左知道求出，这就是我们要的结果！

    public int getTranslateCount(int n) {
        if (n < 0)
            return 0;
        return count(String.valueOf(n));
    }

    private int count(String num) {
        int len = num.length();
        int[] counts = new int[len];
        // f(n -1)必然为1  最后一位的翻译方法
        counts[len - 1] = 1;

        for (int i = len - 2; i >= 0; i--) {
            // 再将字母转换成数字
            int high = num.charAt(i) - '0';
            int low = num.charAt(i + 1) - '0';
            // 计算两位数的值
            int combineNum = high * 10 + low;
            if (combineNum >= 10 && combineNum <= 25) {
                // f(i) = f(i+1) +f(i+2),if中因为f(i+2)不存在，但是该值肯定为1
                if (i == len - 2)
                    counts[i] = counts[i + 1] + 1;
                else
                    counts[i] = counts[i + 1] + counts[i + 2];
            } else {
                // f(i) = f(i+1)
                counts[i] = counts[i + 1];
            }

        }
        // 从第一个数字开始的不同翻译数目
        return counts[0];
    }

上面的代码就是把公式翻译了一遍，其中counnts数组存放每一步计算的结果，即保存~的值。说明只有一位数，必然只有一种翻译方法；同样注意，当时候，将超出范围，需要特别处理，这种情况就是说，对于两位数比如18，肯定有两种翻译方法，即种。

最后一步得到counts[0]即返回即为答案。

这种方法只需遍历数字的每一位即可，实现了题目的要求计算出了翻译数目，但是没有办法表示出翻译结果。