LC 639. 解码方法 II
题目描述
这是 LeetCode 上的 639. 解码方法 II ，难度为 困难。
一条包含字母 A-Z 的消息通过以下的方式进行了编码：1
2
3
4'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，”11106” 可以映射为：
- “AAJF” 对应分组 (1 1 10 6)
- “KJF” 对应分组 (11 10 6)
注意，像 (1 11 06) 这样的分组是无效的，因为 “06” 不可以映射为 ‘F’ ，因为 “6” 与 “06” 不同。
除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 ‘1’ 到 ‘9’ 的任一数字（不包括 ‘0’）。例如，编码字符串 "1*" 可以表示 “11”、”12”、”13”、”14”、”15”、”16”、”17”、”18” 或 “19” 中的任意一条消息。对 “1*” 进行解码，相当于解码该字符串可以表示的任何编码消息。
给你一个字符串 s ，由数字和 ‘*’ 字符组成，返回 解码 该字符串的方法 数目 。
由于答案数目可能非常大，返回对 $10^9 + 7$ 取余 的结果。
示例 1：1
2
3
4
5
6
7输入：s = "*"
输出：9
解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。
可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。
因此，"*" 总共有 9 种解码方法。
示例 2：1
2
3
4
5
6
7输入：s = "1*"
输出：18
解释：这一条编码消息可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条。
每种消息都可以由 2 种方法解码（例如，"11" 可以解码成 "AA" 或 "K"）。
因此，"1*" 共有 9 * 2 = 18 种解码方法。
示例 3：1
2
3
4
5
6
7输入：s = "2*"
输出：15
解释：这一条编码消息可以表示 "21"、"22"、"23"、"24"、"25"、"26"、"27"、"28" 或 "29" 中的任意一条。
"21"、"22"、"23"、"24"、"25" 和 "26" 由 2 种解码方法，但 "27"、"28" 和 "29" 仅有 1 种解码方法。
因此，"2*" 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。
提示：
- $1$ <= s.length <= $10^5$
- s[i] 是
0-9中的一位数字或字符 ‘*’
分情况讨论 DP
这是一道普通的线性 DP 题（之所以说普通，是因为状态定义比较容易想到），也是 （题解）91. 解码方法 的进阶题。
我们称一个解码内容为一个 item。
定义 $f[i]$ 为考虑以 $s[i]$ 为结尾的字符串，共有多少种解码方案。
那么最终答案为 $f[n - 1]$，同时我们有显而易见的起始状态 f[0] = s[0] == '*' ? 9 : (s[0] != '0' ? 1 : 0).
不失一般性考虑 $f[i]$ 该如何转移，$s[i]$ 要么是 *，要么是数字，对应一个分情况讨论过程：
当 $s[i]$ 为
*：此时考虑 $s[i]$ 是单独作为一个item，还是与上一个字符共同作为一个item:- $s[i]$ 单独作为一个
item：由于*可以代指数字1-9，因此有 $f[i] = f[i - 1] * 9$； - $s[i]$ 与上一个字符共同作为一个
item：此时需要对上一个字符 $s[j]$ 进行讨论：- $s[j]$ 为数字
1：此时 $s[i]$ 可以代指1-9，对应了item为11-19这 $9$ 种情况，此时有 $f[i] = f[i - 2] 9$（*如果 $f[i - 2]$ 取不到，则使用 $1$ 代指，下面同理）； - $s[j]$ 为数字
2：此时 $s[i]$ 可以代指1-6，对应了item为21-26这 $6$ 种情况，此时有 $f[i] = f[i - 2] * 6$； - $s[j]$ 为字符
*：此时两个*对应了合法方案为 $11-19$ 和 $21-26$ 共 $15$ 种方案，此时有 $f[i] = f[i - 2] * 15$；
- $s[j]$ 为数字
- $s[i]$ 单独作为一个
当 $s[i]$ 为数字：此时可以从「前一字符 $s[j]$ 为何种字符」和「当前 $s[i]$ 是否为 $0$」出发进行讨论:
- $s[j]$ 为字符
*，根据当前 $s[i]$ 是否为 $0$ 讨论：- $s[i]$ 为数字 $0$：此时 $s[i]$ 无法独自作为一个
item，只能与 $s[j]$ 组合，对应了 $10$ 和 $20$ 两种情况，此时有 $f[i] = f[i - 2] * 2$； - $s[i]$ 为数字
1-9，此时首先有 $s[i]$ 可以作为一个独立item的情况，即有 $f[i] = f[i - 1]$，然后对 $s[i]$ 的数值大小进一步分情况讨论：- $s[i]$ 为数字
1-6，此时 $s[j]$ 可以代指 $1$ 和 $2$，对应了方案 $1x$ 和 $2x$，此时有 $f[i] = f[i - 2] * 2$； - $s[i]$ 为数字
7-9，此时 $s[j]$ 可以代指 $1$，对应方案 $1x$，此时有 $f[i] = f[i - 2]$；
- $s[i]$ 为数字
- $s[i]$ 为数字 $0$：此时 $s[i]$ 无法独自作为一个
- $s[j]$ 为数字类型，此时从「当前 $s[i]$ 是否为 $0$」出发进行讨论：
- $s[i]$ 为数字 $0$：此时 $s[j]$ 只有为 $1$ 和 $2$ 时，才是合法方案，则有 $f[i] = f[i - 2]$；
- $s[i]$ 为数字
1-9：此时首先有 $s[i]$ 可以作为一个独立item的情况，即有 $f[i] = f[i - 1]$，然后再考虑能够与 $s[j]$ 组成合法item的情况：- $s[j]$ 为数值 $1$：此时有 $f[i] = f[i - 2]$；
- $s[j]$ 为数值 $2$，且 $s[i]$ 为数值
1-6：此时有 $f[i] = f[i - 2]$。
- $s[j]$ 为字符
由于是求方案数，因此最终的 $f[i]$ 为上述所有的合法的分情况讨论的累加值，并对 $1e9+ 7$ 取模。
一些细节：实现上了避免大量对 $f[i - 2]$ 是否可以取得的讨论，我们可以对
s前追加一个空格作为哨兵（无须真正插入），以简化代码，同时由于 $f[i]$ 只依赖于 $f[i - 1]$ 和 $f[i - 1]$，可以使用「滚动数组」的形式进行空间空间优化（见 $P2$）。另外，对于「滚动数组」的空间优化方式，还需要说明两点：转移前先使用变量保存
(i-1)%3和(i-2)%3的计算结果，防止大量的重复计算；不能再偷懒使用toCharArray，只能使用charAt，因为 Java 为了遵循字符串不变的原则，会在调用toCharArray时返回新数组，这样复杂度就还是 $O(n)$ 的。
诸如此类的「滚动数组」优化方式，最早在 这里 讲过。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62class Solution {
int mod = (int)1e9+7;
public int numDecodings(String s) {
char[] cs = s.toCharArray();
int n = cs.length;
long[] f = new long[n];
f[0] = cs[0] == '*' ? 9 : (cs[0] != '0' ? 1 : 0);
for (int i = 1; i < n; i++) {
char c = cs[i], prev = cs[i - 1];
if (c == '*') {
// cs[i] 单独作为一个 item
f[i] += f[i - 1] * 9;
// cs[i] 与前一个字符共同作为一个 item
if (prev == '*') {
// 11 - 19 & 21 - 26
f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 15;
} else {
int u = (int)(prev - '0');
if (u == 1) {
f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 9;
} else if (u == 2) {
f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 6;
}
}
} else {
int t = (int)(c - '0');
if (prev == '*') {
if (t == 0) {
f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 2;
} else {
// cs[i] 单独作为一个 item
f[i] += f[i - 1];
// cs[i] 与前一个字符共同作为一个 item
if (t <= 6) {
f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 2;
} else {
f[i] += i - 2 >= 0 ? f[i - 2] : 1;
}
}
} else {
int u = (int)(prev - '0');
if (t == 0) {
if (u == 1 || u == 2) {
f[i] += i - 2 >= 0 ? f[i - 2] : 1;
}
} else {
// cs[i] 单独作为一个 item
f[i] += (f[i - 1]);
// cs[i] 与前一个字符共同作为一个 item
if (u == 1) {
f[i] += i - 2 >= 0 ? f[i - 2] : 1;
} else if (u == 2 && t <= 6) {
f[i] += i - 2 >= 0 ? f[i - 2] : 1;
}
}
}
}
f[i] %= mod;
}
return (int)(f[n - 1]);
}
}
1 | |
- 时间复杂度：$O(n)$
- 空间复杂度：使用「滚动数组」进行优化，复杂度为 $O(1)$，否则为 $O(n)$
枚举 DP
上述解法之所以复杂，是因为不仅仅要对当前字符 $s[i]$ 分情况讨论，还需要对上一个字符 $s[j]$ 分情况讨论。
事实上，我们可以利用解码对象只有 A-Z 来进行枚举。
在从前往后处理字符串 s 时，枚举 $s[i]$ 参与构成的解码内容 item 是字母 A-Z 中哪一个，从而将分情况讨论转变成对应位的字符对比。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution {
int mod = (int)1e9+7;
public int numDecodings(String s) {
int n = s.length();
long[] f = new long[3];
f[0] = 1;
for (int i = 1; i <= n; i++) {
char c = s.charAt(i - 1);
int t = c - '0';
long cnt = 0;
int p1 = (i - 1) % 3, p2 = (i - 2) % 3;
// 枚举组成什么 item（A -> 1; B -> 2 ...）
for (int item = 1; item <= 26; item++) {
if (item < 10) { // 该 item 由一个字符组成
if (c == '*' || t == item) cnt += f[p1];
} else { // 该 item 由两个字符组成
if (i - 2 < 0) break;
char prev = s.charAt(i - 2);
int u = prev - '0';
int a = item / 10, b = item % 10;
if ((prev == '*' || u == a) && (t == b || (c == '*' && b != 0))) cnt += f[p2];
}
}
f[i % 3] = cnt % mod;
}
return (int)(f[n % 3]);
}
}
- 时间复杂度：$O(n * C)$，其中 $C$ 为解码内容字符集大小，固定为 $26$
- 空间复杂度：$O(1)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.639 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
