每日一题 - 剑指 Offer 46. 把数字翻译成字符串

题目信息

• 时间： 2019-07-02

• 题目链接：Leetcode

• tag： 动态规划

• 难易程度：中等

• 题目描述：

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

示例:

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

提示

1. 0 <= num < 2^31

解题思路

本题难点

当数字中包含两位数时，存在两种不同的组合情况。

具体思路

动态规划：
$$
\begin{array}{l}
\text { num }=x_{1} x_{2} \ldots x_{i-2} x_{i-1} x_{i} \ldots x_{n-1} x_{n} \
\text { (例如 }\left.: \quad 12258=x_{1} x_{2} x_{3} x_{4} x_{5}\right) \
\
{\left[\begin{array}{l}
\text { 设 } x_{1} x_{2} \ldots x_{i-2} \text { 的翻译方案数量为 } f(i-2) \
\text { 设 } x_{1} x_{2} \ldots x_{i-2} x_{i-1} \text { 的翻译方案数量为 } f(i-1)
\end{array}\right.}
\end{array}
$$

$$
\left{\begin{array}{ll}
\text { 当整体翻译 } x_{i-1} x_{i} \text { 时, } & x_{1} x_{2} \ldots x_{i-2} x_{i-1} x_{i} \text { 的方案数为 } f(i-2) \
\text { 当单独翻译 } x_{i} \text { 时, } & x_{1} x_{2} \ldots x_{i-2} x_{i-1} x_{i} \text { 的方案数为 } f(i-1)
\end{array}\right.
$$

递推关系：
$$
f(i)=\left{\begin{array}{cc}
f(i-2)+f(i-1) & , \text { 若数字 } x_{i-1} x_{i} \text { 可被翻译 } \
f(i-1) & , \text { 若数字 } x_{i-1} x_{i} \text { 不可被翻译 }
\end{array}\right.
$$

$$
d p[i]=\left{\begin{array}{ll}
d p[i-1]+d p[i-2] & , 10 x_{i-1}+x_{i} \in[10,25] \
d p[i-1] & , 10 x_{i-1}+x_{i} \in[0,10) \cup(25,99]
\end{array}\right.
$$

注意：dp[0]=dp[1]=1 ，即 “无数字” 和 “第 1 位数字” 的翻译方法数量均为 1

代码

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1 ,b = 1;
        for(int i = 2 ; i <= s.length(); i++){
            String tmp = s.substring(i - 2, i);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a+b:a;
            b = a;
            a = c;
        }
        return a;
    }
}

复杂度分析：

• 时间复杂度 O(N) ： N 为字符串 s的长度（即数字 num 的位数 log?(num)），其决定了循环次数。
• 空间复杂度 O(N) ： 字符串 s使用 O(N) 大小的额外空间。

其他优秀解答

解题思路

利用求余运算 num%10 和求整运算 num/10 ，可获取数字 num 的各位数字（获取顺序为个位、十位、百位…）。因此，可通过 求余 和 求整 运算实现 从右向左 的遍历计算。动态规划 “对称性” ，可知从右向左的计算是正确的。

代码

class Solution {
    public int translateNum(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num != 0) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
}

每日一题 - 剑指 Offer 46. 把数字翻译成字符串

原文：https://www.cnblogs.com/ID-Wangqiang/p/13233471.html