当前位置：首页 > news >正文

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

news 2026/3/27 3:58:36

1.题目

描述

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

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

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

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

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

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

示例1

输入：

"12"

返回值：

说明：

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

示例2

输入：

"31717126241541717"

返回值：

说明：

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

3.编码实现

核心代码如下：

func solve(nums string) int {// write code here//排除0if 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]=1dp[0] = 1dp[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/ep1375309
Java编码：https://www.bilibili.com/cheese/play/ep1368535
Golang编码：https://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]）。