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

题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：

0 翻译成 “a” ，1 翻译成 “b”，……，

11 翻译成 “l”，……，25 翻译成 “z”。

一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

1
2
3

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

方法：动态规划

• 状态定义

  • dp[i] 代表以xi 结尾数字的翻译方案数量

• 初始化
  • 初始化 dp[0] = 1 dp[1] = 1 (无数字和第一位数字)翻译方法数量均为1。
  • 无数字：当num的 第一，第二位组成的数字在10~25之间的时候，显然有两种翻译方法，即dp[2] = dp[1] + dp[0] = 2, 而显然dp[1] = 1，因此推出dp[0] = 1。

• 状态转移(注意区间)

• 返回值
  • 返回数组最后一个元素

算法：遍历：

1. 为方便获取数字的各位xi ，考虑先将数字 num 转化为字符串 s，通过遍历 s 实现动态规划。
2. 通过字符串切片s[i-2:i] 获得数字组合10xi-1 + xi，通过对比字符串的ASCII码来判断字符串对应的数字区间。
3. 空间使用优化：由于dp[i]只和 dp[i-1]有关，因此可使用两个变量a,b 分别记录dp[i] 和dp[i-1],两个变量交替前进即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int translateNum(int num) {
        // 数组转为字符串
        String s = String.valueOf(num);

        // 初始化dp[0] = 1,dp[1] = 1
        int a = 1;
        int b = 1;

        // 从数字第3位开始状态转移
        for (int i = 2; i <= s.length(); i++) {
            // 截取dp[i - 2] 和 dp[i - 1]
            String tmp = s.substring(i - 2,i);
            // 判读tmp可不可以进行整体判断
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;

            // 更新dp变量
            b = a;
            a = c;
        }
        return a;
    }
}

复杂度分析

• 时间复杂度：遍历一次字符串的时间复杂度。
• 空间复杂度：字符串的大小O(N)的额外空间。