友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
639. 解码方法 II
一条包含字母 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 不同。
除了 上面描述的数字字母映射方案，编码消息中可能包含 字符，可以表示从 1 到 9 的任一数字（不包括 0）。例如，编码字符串 1 可以表示 11、12、13、14、15、16、17、18 或 19 中的任意一条消息。对 1* 进行解码，相当于解码该字符串可以表示的任何编码消息。
给你一个字符串 s，由数字和 * 字符组成，返回 解码 该字符串的方法 数目。
由于答案数目可能非常大，返回 109 + 7 的 模 。
示例 1：
输入：s = "*" 输出：9 解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。 可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。 因此，"*" 总共有 9 种解码方法。
示例 2：
输入：s = "1*" 输出：18 解释：这一条编码消息可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条。 每种消息都可以由 2 种方法解码（例如，"11" 可以解码成 "AA" 或 "K"）。 因此，"1*" 共有 9 * 2 = 18 种解码方法。
示例 3：
输入：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 <= 105 -
s[i]是0 - 9中的一位数字或字符*
思路分析
动态规划：类似爬楼梯，比爬楼梯复杂！
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-15 08:43:34
*/
public int numDecodings(String s) {
int MOD = 1_000_000_007;
long a = 0, b = 1, c = 0;
for (int i = 1; i <= s.length(); i++) {
c = b * check1Digit(s.charAt(i - 1)) % MOD;
if (i > 1) {
c = (c + (a * check2Digit(s.charAt(i - 2), s.charAt(i - 1))) % MOD) % MOD;
}
a = b;
b = c;
}
return (int) c;
}
private int check1Digit(char c) {
if (c == '0') {
return 0;
}
return c == '*' ? 9 : 1;
}
private long check2Digit(char h, char t) {
if (h == '*' && t == '*') {
return 15;
}
if (h == '*') {
return t <= '6' ? 2 : 1;
}
if (t == '*') {
if (h == '1') {
return 9;
}
if (h == '2') {
return 6;
}
return 0;
}
return (h != '0' && (h - '0') * 10 + (t - '0') <= 26) ? 1 : 0;
}