19、剑指 Offer 46. 把数字翻译成字符串
一、题目
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：
0 <= num < 2^31
二、解法
2.1、动态规划 + 字符串遍历
核心思路
动态规划推导过程：
根据题意，$ num = x_{1} x_{2} \ldots x_{i-2} x_{i-1} x_{i} \ldots x_{n-1} x_{n} $
记数字 num 第 i 位数字为 $ x_{i} $
例如 $ 12258 = x_{1} x_{2} x_{3} x_{4} x_{5} $
- 当整体翻译 $ x_{1} x_{2} $ 时，$ x_{1} x_{2} x_{3} x_{4} x_{5} $ 的方案数为 $ f(i-2) $
- 当单独翻译 $ x_{1} $ 时，$ x_{1} x_{2} x_{3} x_{4} x_{5} $ 的方案数为 $ f(i-1) $
方案的递推关系：
$ f(i)=\left\{\begin{array}{c}f(i-2)+f(i-1), \text { 若数字 } x_{i-1} x_{i} \text { 可被翻译 } \\ f(i-1), \text { 若数字 } x_{i-1} x_{i} \text { 不可被翻译 }\end{array}\right. $根据题意，可被翻译的两位数区间：$ x_{i-1}=0 $ 时，组成的两位数是无法被翻译的（例如 00, 01, 02,⋯ ），因此区间为 [10, 25] 。
因此，状态转移方程：
$ dp[i]= \begin{cases}d p[i-1]+d p[i-2] & , 10 x_{i-1}+x_{i} \in[10,25] \ d p[i-1] & , 10 x_{i-1}+x_{i} \in[0,10) \cup(25,99]\end{cases} $
初始状态：dp[0] = dp[1] = 1 ，即 “无数字” 和 “第 1 位数字” 的翻译方法数量均为 1
当 num 第 1,2 位的组成的数字 ∈[10,25] 时，显然应有 2 种翻译方法，即 dp[2] = dp[1] + dp[0] = 2 ，而显然 dp[1] = 1 ，因此推出 dp[0] = 1 。
字符串遍历法：
为获取数字的各位 $ x_{i} $ ，考虑先将数字 $ num $ 转化为字符串 s ，通过遍历 s 实现动态规划。
空间使用优化： 由于 dp[i] 只与 dp[i - 1] 有关，因此可使用两个变量 a, b 分别记录 dp[i], dp[i - 1] ，两变量交替前进即可。此方法可省去 dp 列表使用的 O(N) 的额外空间。
复杂度分析
时间复杂度：O(N)，N 为字符串 s 的长度（即数字 num 的位数 log(num) ），其决定了循环次数。
空间复杂度：O(N)，字符串 s 使用 O(N) 大小的额外空间。
Code
class Solution {
public int translateNum(int num) {
// int 转为字符串
String s = String.valueOf(num);
// dp[1]=dp[0]=1, a b 作为缓存变量, 替代 dp 数组, 节省空间
int a = 1, b = 1;
// 从 dp[2] 开始算
for (int i = 2; i <= s.length(); i++) {
// 向前取两位字符
String tmp = s.substring(i - 2, i);
// c=dp[i], 判断 tmp 是否在区间 [10,25] 中
// * 若在, 令 dp[i]=dp[i-1]+dp[i-2], 即 c=a+b
// * 若不在, 令 dp[i]=dp[i-1]
int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
// 更新 dp[i] 前, 将 dp[i-1] 的值存入 dp[i-2], 即 b=a
b = a;
// 更新 dp[i]
a = c;
}
return a;
}
}
2.2、动态规划 + 数字求余
核心思路
此题的动态规划计算是 对称 的 ，即 从左向右 遍历（从第 dp[2] 计算至 dp[n] ）和 从右向左 遍历（从第 dp[n - 2] 计算至 dp[0] ）所得方案数一致。
上述方法虽然已经节省了 dp 列表的空间占用，但字符串 s 仍使用了 O(N) 大小的额外空间。
利用求余运算 num % 10 和求整运算 num // 10 ，可获取数字 num 的各位数字（获取顺序为个位、十位、百位…）。
自此，字符串 s 的空间占用也被省去，空间复杂度从 O(N) 降至 O(1) 。
复杂度分析
时间复杂度：O(N) ，N 为字符串 s 的长度（即数字 num 的位数 log(num) ），其决定了循环次数。
空间复杂度：O(1) ，几个变量使用常数大小的额外空间。
Code
class Solution {
public int translateNum(int num) {
int a = 1, b = 1, x, y = num % 10;
while(num != 0) {
num /= 10;
x = num % 10;
int tmp = 10 * x + y;
int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
b = a;
a = c;
y = x;
}
return a;
}
}