可视化图解算法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]构成）。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python编码：https://www.bilibili.com/cheese/play/ep1375309https://www.bilibili.com/cheese/play/ep1375309

• Java编码：https://www.bilibili.com/cheese/play/ep1368535https://www.bilibili.com/cheese/play/ep1368535

• Golang编码：https://www.bilibili.com/cheese/play/ep1368735https://www.bilibili.com/cheese/play/ep1368735

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编码：https://www.bilibili.com/cheese/play/ep1375309https://www.bilibili.com/cheese/play/ep1375309

• Java编码：https://www.bilibili.com/cheese/play/ep1368535https://www.bilibili.com/cheese/play/ep1368535

• Golang编码：https://www.bilibili.com/cheese/play/ep1368735https://www.bilibili.com/cheese/play/ep1368735

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编码实现：https://www.bilibili.com/cheese/play/ss897667807https://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：https://www.bilibili.com/cheese/play/ss161443488https://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：https://www.bilibili.com/cheese/play/ss63997https://www.bilibili.com/cheese/play/ss63997

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

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