题目信息

  • 题目：剑指 Offer 46. 把数字翻译成字符串

  • 时间： 2020-08-26

  • 题目链接：Leetcode

  • tag： 动态规划

  • 难易程度：中等

  • 题目描述：

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

示例:

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

提示

1
1. 0 <= num < 2^31

解题思路

本题难点

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

具体思路

动态规划：

 num =x1x2…xi−2xi−1xi…xn−1xn (例如 :12258=x1x2x3x4x5)[ 设 x1x2…xi−2 的翻译方案数量为 f(i−2) 设 x1x2…xi−2xi−1 的翻译方案数量为 f(i−1)\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}

{ 当整体翻译 xi−1xi 时, x1x2…xi−2xi−1xi 的方案数为 f(i−2) 当单独翻译 xi 时, x1x2…xi−2xi−1xi 的方案数为 f(i−1)\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.

NzK1dH.png

递推关系：

f(i)={f(i−2)+f(i−1), 若数字 xi−1xi 可被翻译 f(i−1), 若数字 xi−1xi 不可被翻译 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.

dp[i]={dp[i−1]+dp[i−2],10xi−1+xi∈[10,25]dp[i−1],10xi−1+xi∈[0,10)∪(25,99]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.

NzMptA.png

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
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 的各位数字（获取顺序为个位、十位、百位…）。因此，可通过 求余 和 求整 运算实现 从右向左 的遍历计算。动态规划 “对称性” ，可知从右向左的计算是正确的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
    }
}