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. 代码如下: