面试题 46. 把数字翻译成字符串
题目描述
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258 输出: 5 解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示:
0 <= num < 231
解法
方法一:记忆化搜索
我们先将数字 num
转为字符串 $s$,字符串 $s$ 的长度记为 $n$。
然后我们设计一个函数 $dfs(i)$,表示从第 $i$ 个数字开始的不同翻译的数目。那么答案就是 $dfs(0)$。
函数 $dfs(i)$ 的计算如下:
- 如果 $i \ge n - 1$,说明已经翻译到最后一个数字,只有一种翻译方法,返回 $1$;
- 否则,我们可以选择翻译第 $i$ 个数字,此时翻译方法数目为 $dfs(i + 1)$;如果第 $i$ 个数字和第 $i + 1$ 个数字可以组成一个有效的字符(即 $s[i] == 1$ 或者 $s[i] == 2$ 且 $s[i + 1] \lt 6$),那么我们还可以选择翻译第 $i$ 和第 $i + 1$ 个数字,此时翻译方法数目为 $dfs(i + 2)$。因此 $dfs(i) = dfs(i+1) + dfs(i+2)$。
过程中我们可以使用记忆化搜索,将已经计算过的 $dfs(i)$ 的值存储起来,避免重复计算。
时间复杂度 $O(\log num)$,空间复杂度 $O(\log num)$。其中 $num$ 为给定的数字。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
方法二:动态规划
我们可以将方法一中的记忆化搜索改为动态规划。
定义 $f[i]$ 表示前 $i$ 个数字的不同翻译的数目,那么答案就是 $f[n]$。初始化 $f[0] = 1$, $f[1] = 1$。
我们可以从前往后计算 $f[i]$ 的值,对于每个 $i$,我们可以选择翻译第 $i$ 个数字,此时翻译方法数目为 $f[i - 1]$;如果第 $i-1$ 个数字和第 $i$ 个数字可以组成一个有效的字符(即 $s[i - 1] == 1$ 或者 $s[i - 1] == 2$ 且 $s[i] \lt 6$),那么我们还可以选择翻译第 $i - 1$ 和第 $i$ 个数字,此时翻译方法数目为 $f[i - 2]$。因此 $f[i] = f[i-1] + f[i-2]$。
由于 $f[i]$ 只与 $f[i - 1]$ 和 $f[i - 2]$ 有关,因此我们可以只用两个变量来存储 $f[i - 1]$ 和 $f[i - 2]$ 的值,从而省去数组 $f$ 的空间。
时间复杂度 $O(\log num)$,空间复杂度 $O(\log num)$。其中 $num$ 为给定的数字。
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|