# 剑指 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];

    }
}