把数字翻译成字符串

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

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

示例 1:

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

提示：

• 0 <= num < 231

将 12258 的每一位翻译为一个字母得到 “bccfi”；

将 12258 中的 22 翻译为 “w” ，其他的每一位翻译为一个字母得到 “bwfi”；

可以总结出翻译的规则，字符串的 i 位置：

• 可以单独作为一位来翻译
• 如果第 i - 1 位和第 i 位组成的数字在 10 到 25 之间，可以把这两位连起来翻译

用 f(i) 表示以第 i 位结尾的前缀串翻译的方案数，考虑每一位单独翻译和前一位连起来再翻译的贡献。单独翻译对 f(i) 的贡献为 f(i - 1)；如果第 i - 1 位存在，第 i - 1位和第 i 位连起来的数字 x 满足 10 <= x <= 25，那么可以连起来翻译，对 f(i) 的贡献为 f(i - 2)，否则为 0。

我们可以列出下面的动态规划转移方程：

f(i) = f(i - 1) + f(i - 2) ( i - 1 >= 0，10 <= x <= 25)

class Solution {
    public int translateNum(int num) {
        String src = String.valueOf(num);
        int p = 0, q = 0, r = 1;
        for(int i = 0; i < src.length(); i++){
            p = q;
            q = r;
            if(i == 0){
                continue;
            }
            String pre = src.substring(i - 1, i + 1);
            if(pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0){
                r += p;
            }
        }
        return r;
    }
}

时间复杂度 O(log n)，空间复杂度O(logn)。