面试题46. 把数字翻译成字符串(简单)

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

示例 1:

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

提示：

0 <= num < 231

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof

思路：

动态规划思路

dp[i]表示以数字num[i]结尾的翻译方案数

如果i和i-1位组合可以翻译的话，也就是在10到25之间的话，dp[i]=dp[i-1]+dp[i-2];

如果不能翻译，则就是dp[i]=dp[i-1];

由于单独取字符比较麻烦，直接用字符串进行比较方便

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int translateNum(int num) {
        //dp设为以当前数字结尾的翻译方案数
        //dp[i]=dp[i-1]+dp[i-2],如果后面两位可以翻译的话
        //dp[i]=dp[i-1],如果后面两位不可以翻译的话，也就是0-10，25-99之间
        String s = String.valueOf(num);
        int a=1,b=1;
        for(int i=2;i<=s.length();i++){
            String substr = s.substring(i-2,i);//每两位一判断
            int c = substr.compareTo("10")>=0 &&substr.compareTo("25")<=0 ?a+b:a;
            b=a;
            a=c;
        }
        return a;
    }
}