剑指 Offer 46. 把数字翻译成字符串
一、题目描述
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
一个数字可能有多个翻译。
请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：
0 <= num < 231
二、题目解析
为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：
三、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
public int translateNum(int num) {
// 将 int 变量 num 转换成字符串
String s = String.valueOf(num);
// dp[i] 表示前 i 位可以解码的总数
// dp[0] 表示前 0 位可以解码的总数
// dp[1] 表示前 1 位可以解码的总数
int[] dp = new int[s.length()];
// dp[0] 表示前 0 位可以解码的总数
dp[0] = 1;
// 通过 for 循环填充 dp 数组
for (int i = 1; i < s.length(); i++) {
// 在当前遍历的过程中，第 i 个字符为倒数第一个字符
// 那么第 i - 1 就是倒数第二个字符
// 1、如果发现第 i - 1 的字符为 1
// 2、或者发现第 i - 1 的字符为 2 并且第 i 个字符的值小于等于 5
// 这两个判断条件指的值当前遍历的字符的倒数两个字符为
// 10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25
if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && (s.charAt(i) <= '5'))) {
// 如果 i == 1，说明此时只有两个数字，那么 i - 2 是不存在的
// 对于这种情况有两种翻译方法，比如 num = 14
// 1、两个数字单独拿出来翻译 1 翻译为 b，4 翻译为 e，结果就是 be
// 2、直接把 14 翻译为字母 ，结果就是 o
// 所以 dp[i] = 2
if (i == 1) {
//有两种翻译方法
dp[i] = 2;
// 否则的话，说明遍历的字符串有三个数字了
// 并且最后两个数字可以翻译为字母
} else {
// 那么此时 dp[i] = dp[i - 1] + dp[i - 2];
dp[i] = dp[i - 1] + dp[i - 2];
}
// 如果最后两个数字组合在一起都无法翻译为字母
// 比如 1258，最后两个数字 58 无法翻译为字母，8 只能单独翻译，所以方法数和 125 一样
} else {
// 那么 dp[i] = dp[i - 1]
dp[i] = dp[i - 1];
}
}
// dp[s.length() - 1] 表示前 s.length() - 1 位可以解码的总数
return dp[s.length() - 1];
}
}
