剑指 Offer 46. 把数字翻译成字符串

题意：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

解题思路

解法：
1.分析题意，我们需要将num转为字符串，我们定义，T[n]为字符串长度n的子串的翻译种类个数
2.思考一下，T[n]、T[n-1]、numString[n]、numString[n-1]关系
3.推导可知，if numString[n]与numString[n-1]可以组成数字，则T[n]=T[n-1]+T[n-2]
4.if numString[n]与numString[n-1]不可以组成数字，则T[n]=T[n-1]
5.能否组成数字在于两个条件，如果1==numString[n-1] || （numString[n-1]==2 && numString[n]<=5）成立，则证明可以组成数字

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
class Solution {
    public static void main(String[] args) {
        translateNum(18580);
    }
    public static int translateNum(int num) {
        // 分析题意，我们需要将num转为字符串，我们定义，T[n]为字符串长度n的子串的翻译种类个数
        // 思考一下，T[n]、T[n-1]、numString[n]
        // 推导可以，if numString[n]与numString[n-1]可以组成数字，则T[n]=3+T[n-2]
        // if numString[n]与numString[n-1]不可以组成数字，则T[n]=T[n-1]
        // 能否组成数字在于1<=numString[n-1]<=2 && numString[n]<=5
        String numString = String.valueOf(num);
        if (numString.length() <= 1) {
            return 1;
        }

        if (numString.length() == 2) {
            return isE(numString.charAt(0) - '0', numString.charAt(1) - '0')
                    ? 2
                    : 1;
        }

        int t0 = 1,
                t1 = isE(numString.charAt(0) - '0', numString.charAt(1) - '0')
                        ? 2
                        : 1,
                tn = 1;
        for (int i = 2; i < numString.length(); i++) {
            if (isE(numString.charAt(i - 1) - '0', numString.charAt(i) - '0')) {
                tn = t1 + t0;
            } else {
                tn = t1;
            }
            t0 = t1;
            t1 = tn;
        }
        return tn;
    }

    public static boolean isE(int a, int b) {
        if (a == 1) {
            return true;
        }

        if (a == 2 && b <= 5) {
            return true;
        }
        return false;
    }
}