可视化图解算法79：把数字翻译成字符串(解密数字)

1.题目

描述

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

我们把一个字符串编码成一串数字，再考虑逆向编译成字符串。

由于没有分隔符，数字编码成字母可能有多种编译结果，例如 11 既可以看做是两个 'a' 也可以看做是一个 'k' 。但 10 只可能是 'j' ，因为 0 不能编译成任何结果。

现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0 < n≤90

进阶：空间复杂度 O(n)，时间复杂度 O(n)

示例1

输入：

"12"

返回值：

2

说明：

2种可能的译码结果（”ab” 或”l”） 注：l为L，并发123的1.

示例2

输入：

"31717126241541717"

返回值：

192

说明：

192种可能的译码结果

2. 题解思路

本题的难点是根据题意对数字破译的情况进行细分，大致分为3种情况。

• 情况1：无法破译的情况。当0的前面不是1或2时，无法译码，0种 （比如：00,30,40等）
• 情况2：连续的两个数字在11-19，21-26区间之内，破译方法有两种（当前状态由dp[i-1]、dp[i-2]构成）；
• 情况3：不满足情况1、2的时候，破译只有一种，如：10、20、31、86等（当前状态由dp[i-1]构成）。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

3.编码实现

核心代码如下：

func solve(nums string) int {
    // write code here
    //排除0
    if nums == "0" {
        return 0
    }
    //排除无法破译的情况
    for i := 1; i < len(nums); i++ {
        //当0的前面不是1或2时，无法译码，0种 （比如：00,30,40等）
        if nums[i] == '0' {
            if nums[i-1] != '1' && nums[i-1] != '2' {
                return 0
            }
        }
    }
​
    // 1.定义状态.  i：字符串s的下标; dp[i]：s[0:i-1]的编码结果
    dp := make([]int, len(nums)+1)
    // 2.初始化边界条件：(类似于跳台阶、爬楼梯等) dp[0]=1; dp[1]=1
    dp[0] = 1
    dp[1] = 1
    // 3.确定递推公式：
    for i := 2; i <= len(nums); i++ {
        // 对于11-19，21-26，译码方式有可选择的两种方案；其他只能有一种方案：如01-09、10、20
        //todo : if 与else if 分开写 主要是便于理解，可以合并
        if nums[i-2] == '1' && (nums[i-1] > '0' && nums[i-1] <= '9') {
            //在11-19之间的情况
            dp[i] = dp[i-1] + dp[i-2] //递推式
        } else if nums[i-2] == '2' && (nums[i-1] > '0' && nums[i-1] < '7') {
            //21-26之间的情况
            dp[i] = dp[i-1] + dp[i-2] //递推式
        } else {
            //其他数字，如：10、20、31、86等
            dp[i] = dp[i-1]
        }
    }
    // 4.输出结果
    return dp[len(nums)]
​
}

具体完整代码你可以参考下面视频的详细讲解。

• Python编码：B站@好易学数据结构
• Java编码：B站@好易学数据结构
• Golang编码：B站@好易学数据结构

4.总结

本题的难点是对破译数字的情况细分，很容易漏掉，要特别留意。如果对破译的情况细分了解之后，在套用动态规划模板就很容易了。

破译的情况进行细分，大致分为3种情况。

• 情况1：无法破译的情况。当0的前面不是1或2时，无法译码，0种 （比如：00,30,40等）
• 情况2：连续的两个数字在11-19，21-26区间之内，破译方法有两种（当前状态由dp[i-1]、dp[i-2]构成，因此dp[i]=dp[i-1]+dp[i-2]）；
• 情况3：不满足情况1、2的时候，破译只有一种，如：10、20、31、86等（当前状态由dp[i-1]构成，因此dp[i]=dp[i-1]）。

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

✅ 链表

✅ 二叉树

✅ 二分查找、排序

✅ 堆、栈、队列

✅ 回溯算法

✅ 哈希算法

✅ 动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：B站@好易学数据结构
• Java编码实现：B站@好易学数据结构
• Golang编码实现：B站@好易学数据结构

对于LeetCode数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：不积跬步，无以至千里；不积小流，无以成江海。