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

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

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

解题思路

动态规划: 如果最后两个数字能翻译成字符, f(n) = f(n - 1) + f(n - 2)
如果最后两个数字不能翻译成字符, f(n) = f(n - 1)
dp[i] = dp[i - 1] + (isInRange(s, i) ? dp[i - 2] : 0)
由题知, 只有一个字符时, 有一种答案
两个字符时, 如果两个字符在10和25之间, 则有两种, 否则一种
这种做法会额外多一个数组的空间(代码中注释掉的部分)
如果要进一步优化, 则用三个临时变量(没注释的部分), 这时消耗空间与问题规模无关

代码

class Solution {
    public int translateNum(int num) {
        // 如果最后两个数字翻译成字符, f(n) = f(n - 1) + f(n - 2)
        // 否则 f(n) = f(n - 1)
        String s = String.valueOf(num);
        if (s.length() == 1) {
            return 1;
        }
//        int[] dp = new int[s.length()];
//        dp[0] = 1;
//        dp[1] = isInRange(s, 1) ? 2 : 1;
//        for (int i = 2; i < s.length(); i++) {
//            dp[i] = dp[i - 1] + (isInRange(s, i) ? dp[i - 2] : 0);
//        }
//        return dp[s.length() - 1];
        int a = 1;
        int b = isInRange(s, 1) ? 2 : 1;
        int c = b;
        for (int i = 2; i < s.length(); i++) {
            c = b + (isInRange(s, i) ? a : 0);
            a = b;
            b = c;
        }
        return c;
    }

    public boolean isInRange(String s, int i) {
        s = s.substring(i - 1, i + 1);
        return s.compareTo("25") <= 0 && s.compareTo("10") >= 0;
    }

    public boolean isInRange(String s, int i) {
        s = s.substring(i - 1, i + 1);
        return s.compareTo("25") <= 0 && s.compareTo("10") >= 0;
    }
}