剑指Offer-面试题46-把数字翻译成字符串

2020-05-02

题目描述

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

示例1：

1
2
3

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

提示：0 <= num < 2^31

思路

动态规划，流程题解如下：

转移方程：
dp[i] = dp[i -1] + dp[i -2] ,10*x(i-1) + x(i) ∈[10,25]
dp[i] = dp[i -1] ,10*x(i-1) + x(i) ∈[0,10)∪(25,99]
初始状态：dp[0] = dp[1] = 1
流程：

将数字num转化成字符串s，遍历字符串s实现动态规划
字符串切片s[i-2,i]，获取组合10*x(i-1) + x(i)，通过字符串比较判断所属区间
用a，b分别记录dp[i]，dp[i-1]

代码

class Solution{
    public int translationNum(int num){
        //将num转成字符串s
        String s = String.valueOf(num);
        int a = 1;  //dp[i]
        int b = 1;  //dp[i-1]
        int c = 0;
        for(int i=2;i<=s.length();i++){
            //substrirng()左闭右开
            //获取组合
            String temp = str.substring(i-2,i);
            //通过字符串对比得出所属区间，判断组合是否可被整体翻译
            if(temp.compareTo("10")>=0 && temp.compareTo("25")<=0){ //组合可被翻译
                c = a + b;
            }
            else{   //组合不能被翻译
                c = a;
            }
            //更新
            b = a;
            a = c;
        }
        return a;
    }
}

思路参考大佬
作者：jyd
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/mian-shi-ti-46-ba-shu-zi-fan-yi-cheng-zi-fu-chua-6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。