剑指 Offer 46. 把数字翻译成字符串

大家好，我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：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];

    }
}