Keshawn_lu's Blog

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

动态规划
字数统计: 459阅读时长: 2 min
2020/06/09 Share

题目简介：

给定一个数字，我们按照如下规则把它翻译为字符串：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]的意思为下标0 ~ i的字符串翻译方法的数量。

由于单个数字必定能有一种翻译，单独翻译对dp[i]的贡献为dp[i - 1]，所以dp[i] += dp[i - 1]。

如果第i位的数字能与i - 1位的数字构成可翻译的数字X(即10 <= X <= 25)，那么把第i位和第i - 1位看成一个整体，有一种翻译方法，那么此时对dp[i]的贡献为dp[i - 2]，所以dp[i] += dp[i - 2]。

最后返回dp[num_str.size() - 1]即可。

tips:

  • 可在字符串的最前面加0，方便dp数组的初始化。
  • 学会使用substr函数，const char[]类型，在标准C++中不能做 +操作。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int translateNum(int num) {

        string num_str = to_string(num);
        num_str = "0" + num_str;    //最前面加0

        vector<int> dp(num_str.size(), 0); //以i结尾的字符串有多少种翻译方法
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i < num_str.size(); i++){

            dp[i] += dp[i - 1]; //自身可翻译成一种，相当于dp[i - 1]

            //num_str[i - 1] + num_str[i]
            string temp = num_str.substr(i - 1, 2);
            if(temp >= "10" && temp <= "25"){

                //与num_str[i - 1]合并翻译成一种，相当于dp[i - 2]种
                dp[i] += dp[i - 2]; 
            }
        }

        return dp[num_str.size() - 1];

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网