給定一個數(shù)字，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” ，1 翻譯成 “b”，……，11 翻譯成 “l(fā)”，……，25 翻譯成 “z”。一個數(shù)字可能有多個翻譯。請編程實現(xiàn)一個函數(shù)，用來計算一個數(shù)字有多少種不同的翻譯方法。

示例 1:

輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

解題思路

動態(tài)規(guī)劃: 如果最后兩個數(shù)字能翻譯成字符, f(n) = f(n - 1) + f(n - 2)
如果最后兩個數(shù)字不能翻譯成字符, f(n) = f(n - 1)
dp[i] = dp[i - 1] + (isInRange(s, i) ? dp[i - 2] : 0)
由題知, 只有一個字符時, 有一種答案
兩個字符時, 如果兩個字符在10和25之間, 則有兩種, 否則一種
這種做法會額外多一個數(shù)組的空間(代碼中注釋掉的部分)
如果要進一步優(yōu)化, 則用三個臨時變量(沒注釋的部分), 這時消耗空間與問題規(guī)模無關(guān)

代碼

class Solution {
    public int translateNum(int num) {
        // 如果最后兩個數(shù)字翻譯成字符, 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;
    }
}