题目

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

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

解答

方法一:动态规划

问题分解

把数字 num 当成一个数组 nums,子结构就是左边界相同、右边界不同的子数组。在这样一个子数组上的求解,可以由前面子数组的解推导出来。对于某个子数组,它的右边界是第 i 个数字 nums[i],求解在该子数组上的子问题:考虑 nums[i],可以单独翻译它,此时取决于 nums[i-1]子数组的解;也可以把 nums[i]nums[i-1] 组合起来一起翻译(如果满足翻译条件),此时取决于 nums[i-2] 子问题的解。

状态定义

dp[i] 表示 nums[0...i) 这段子数组总共的翻译方法。

状态转移

  • 不满足组合条件:那么只能单独翻译nums[i]dp[i] = dp[i-1]
  • 满足组合条件:即可单独也可以组合翻译,dp[i] = dp[i-1] + dp[i-2]

初始化

空数组的翻译方法数为 1 (不翻译),则 dp[0] = 1

只有一个数字的翻译方法数为 1 ,则 dp[1] = 1

最终结果即为 dp[size]

代码

其实并不需要真的使用 nums 数组,我们只需要知道每一位数字就行。
所以可以对10求余得到每一位数字,注意此时得到的数字是从最右边开始的,所以是逆序计算 dp 数组,但这并不影响结果。

而且也可以不用 dp 数组,我们注意到 dp[i] 只与前两个状态有关,所以可以使用三个变量滚动赋值代替数组。

使用这些技巧,实现起来会比较方便:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int translateNum(int num) {
// pre2表示到nums[i-2]为止可行的翻译方法总数
// pre1表示到nums[i-1]为止可行的翻译方法总数
// cur 表示到nums[i]为止可行的翻译方法总数
int pre2 = 1, pre1 = 1, cur = 1; // 初始化
int t = num % 10, n = 0; // n当前数字,t上一个数字
while(num){ // 获取每一位上的数字
num /= 10;
n = num % 10;
cur = (n != 0 && n*10 + t < 26) ? pre1 + pre2 : pre1;
pre2 = pre1;
pre1 = cur;
t = n;
}
return cur;
}
};

复杂度

  • 时间复杂度 O(log n),取决于数字 num 的位数。
  • 空间复杂度 O(1) ,只使用了常数个变量。