91. 解码方法

题意

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"

'B' -> "2"

...

'Z' -> "26"

解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种

方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)

• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在

映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

难度

中等

示例

示例 1：

输入：s = "12"

输出：2

解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"

输出：3

解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "06"

输出：0

解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

分析

本题我们打算采用 动态规划 的算法来解，很多小伙伴第一次听到动态规划的时候往往会

担心能不能掌握得了，这里给大家吃个定心丸，只要跟着我们的题解走，掌握动态规划就

不是问题（前面其实也讲过，比如说 053.最大子数组和、072.编辑距离等等，相信有些小

伙伴还有印象）。

今天这道算是比较简单的动态规划题了，就让我们一步步来拆解吧。

首先第一步是找到状态，题目要求的是最后 解码 方法的 总数 。

中间的状态是什么呢？

我们把字符串一个个分开，会发现每个前缀字符串都有一个独立答案，且跟前面的前缀字

符串的答案息息相关（即便我们还没找出来其中的关系）。

所以我们可以把状态确定为：f[i] 表示字符串 s 的前 i 个字符 s[1..i] 的解码方法数。

接着就是确定动态转移方程，实际上只有两种情况：

• 只使用了一个字符解码

• 使用两个字符解码

我们需要对两种情况分别讨论转移，因为它们所对应的状态不一样。

• 对于第一种情况，我们知道只要当前字符 s[i]不等于'0'，它就可以解析成某个字母，

所以这时的方案数为 f[i - 1]

• 对于第二种情况，我们知道只要当前字符和前一个字符组合起来小于等于 26，也可

以被解析成某个字母，所以这时候的方案数就是 f[i - 2]

因此我们可以得到动态转移方程：

$ f[i] = { . $

即如果满足上述情况之一就可以转移，两种情况都满足，均可以转移。

最终要确定的就是初始状态。初始状态自然是字符串为空串，这样子就只能有唯一的解码

方法，就是解码出空串，即 f[0]=0。

但是在大多数语言中，字符串是从 0 开始统计位置的，所以我们只需要稍微处理一下细

节，就可以将我们的动态转移方程转化为以下代码。

class Solution {

public int numDecodings(String s) {

// f[i] 表示前 i 个字符的解码方法数。

int[] f = new int[s.length() + 1];

// 初始化 f[0] 为 1，因为一个空字符串只有一种解码方法，即没有解码。

f[0] = 1;

// 从第 1 个字符开始遍历。

for(int i = 1; i <= s.length(); i++) {

 // 如果当前字符不是 '0'，那么当前字符可以单独解码。

if (s.charAt(i - 1) != '0') {

// 当前字符单独解码的方法数等于前 i-1 个字符的解码方法数。

f[i] += f[i - 1];

}

// 如果当前字符与前一个字符组合在一起是一个合法的编码（即在 10-26 范围内）。

if (i >= 2 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 +

(s.charAt(i - 1) - '0') <= 26)) {

// 前 i 个字符的解码方法数增加前 i-2 个字符的解码方法数。

f[i] += f[i - 2];

}

}

// 返回整个字符串的解码方法数。

return f[s.length()];

}

}

f[i] 代表字符串前 i 个字符的解码方法数。

1. 从字符串的第一个字符开始，判断每一个字符是否可以单独解码。例如，‘0’ 不能单

独解码，但 ‘1’ 到 ‘9’ 都可以。如果字符可以单独解码，f[i] 就增加 f[i-1]，因为增加一

个字符后的解码方法数就是前 i-1 个字符的解码方法数。

2. 然后判断当前字符与前一个字符是否可以组合解码。例如，“12” 可以解码为 ‘A’ 和 ‘B’

或 ‘L’。如果它们可以组合解码，f[i] 就增加 f[i-2]，因为增加两个字符后的解码方法

数就是前 i-2 个字符的解码方法数。

在遍历完整个字符串后，f[s.length()] 就是整个字符串的解码方法数。

好，当输入是 226 的时候，让我们来模拟一下整个题解过程。

由于每一个数字可以对应一个字母（1 对应 A, 2 对应 B…26 对应 Z）。我们可以确定给定

的字符串“226”可以解码为多种不同的方法。

对于字符串“226”：

1. 当 i = 1，子串是 “2”：

– 因为 2 不是 0，所以 f[1] += f[0]，即 f[1] = 1。

– 由于 i < 2，我们不考虑两个数字的组合。

2. 当 i = 2，子串是 “22”：

– 因为 2 不是 0，所以 f[2] += f[1]，即 f[2] = 1。

– 接着我们查看“22”是否是一个有效的编码（即是否在 1 到 26 之间）：是的，

所以 f[2] += f[0]，即 f[2] = 2。这表示“22”可以解码为“BB”或者“V”。

3. 当 i = 3，子串是 “226”：

– 因为 6 不是 0，所以 f[3] += f[2]，即 f[3] = 2。

– 接着我们查看“26”是否是一个有效的编码：是的，所以 f[3] += f[1]，即 f[3]

= 3。这表示“226”可以解码为“BZ”, “VF”, 或者 “BBF”。

最终结果为 f[3] = 3。所以，字符串“226”有 3 种解码方式。来看题解效率：

091.%E8%A7%A3%E7%A0%81%E6%96%B9%E6%B3%95-20231017172042.png

总结

其实动态规划题目并不是什么大怪物，关键是按照步骤一步步来，便可以轻松将其解开。

力扣链接：https://leetcode.cn/problems/decode-ways/