Hard
题目描述
一条包含字母 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 <= 10^5
- s[i] 是一位数字或字符 ‘*’
解题思路
这是一个动态规划问题，是解码方法 I 的升级版本，关键是处理通配符 ‘*’。
核心思路是使用动态规划，定义 dp[i] 表示字符串前 i 个字符的解码方案数。对于每个位置，我们需要考虑两种情况：
- 单独解码当前字符
- 和前一个字符一起解码
状态转移方程：
- 如果当前字符可以单独解码，则
dp[i] += dp[i-1] - 如果当前字符和前一个字符可以组成有效的两位数，则
dp[i] += dp[i-2]
处理通配符的关键：
- 单个 ‘*’ 可以代表 1-9，有 9 种选择
- 两位数中的 ‘*’：
- “1*"：可以是 11-19，都有效，有 9 种选择
- “2*"：可以是 21-26 有效，27-29 无效，有 6 种选择
- “*1” 到 “*6”：可以是 11,21 或 16,26，有 2 种选择
- “*7” 到 “*9”：只能是 17,18,19，有 1 种选择
- “**"：需要枚举所有可能的两位数 11-26，有 15 种选择
为了避免重复计算，我们使用滚动数组优化空间复杂度，只需要记录前两个状态即可。
代码实现
class Solution {
public:
int numDecodings(string s) {
const int MOD = 1000000007;
int n = s.length();
// dp[i] 表示前i个字符的解码方案数
long long prev2 = 1; // dp[i-2]
long long prev1 = s[0] == '*' ? 9 : (s[0] == '0' ? 0 : 1); // dp[i-1]
for (int i = 1; i < n; i++) {
long long curr = 0;
// 单个字符解码
if (s[i] == '*') {
curr = (curr + prev1 * 9) % MOD;
} else if (s[i] != '0') {
curr = (curr + prev1) % MOD;
}
// 两个字符一起解码
if (s[i-1] == '1') {
if (s[i] == '*') {
curr = (curr + prev2 * 9) % MOD;
} else {
curr = (curr + prev2) % MOD;
}
} else if (s[i-1] == '2') {
if (s[i] == '*') {
curr = (curr + prev2 * 6) % MOD;
} else if (s[i] <= '6') {
curr = (curr + prev2) % MOD;
}
} else if (s[i-1] == '*') {
if (s[i] == '*') {
curr = (curr + prev2 * 15) % MOD; // 11-19, 21-26
} else if (s[i] <= '6') {
curr = (curr + prev2 * 2) % MOD; // 1x, 2x
} else {
curr = (curr + prev2) % MOD; // 1x only
}
}
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
};
class Solution:
def numDecodings(self, s: str) -> int:
MOD = 10**9 + 7
n = len(s)
# dp[i] 表示前i个字符的解码方案数
prev2 = 1 # dp[i-2]
prev1 = 9 if s[0] == '*' else (0 if s[0] == '0' else 1) # dp[i-1]
for i in range(1, n):
curr = 0
# 单个字符解码
if s[i] == '*':
curr = (curr + prev1 * 9) % MOD
elif s[i] != '0':
curr = (curr + prev1) % MOD
# 两个字符一起解码
if s[i-1] == '1':
if s[i] == '*':
curr = (curr + prev2 * 9) % MOD
else:
curr = (curr + prev2) % MOD
elif s[i-1] == '2':
if s[i] == '*':
curr = (curr + prev2 * 6) % MOD
elif s[i] <= '6':
curr = (curr + prev2) % MOD
elif s[i-1] == '*':
if s[i] == '*':
curr = (curr + prev2 * 15) % MOD # 11-19, 21-26
elif s[i] <= '6':
curr = (curr + prev2 * 2) % MOD # 1x, 2x
else:
curr = (curr + prev2) % MOD # 1x only
prev2 = prev1
prev1 = curr
return prev1
public class Solution {
public int NumDecodings(string s) {
const int MOD = 1000000007;
int n = s.Length;
// dp[i] 表示前i个字符的解码方案数
long prev2 = 1; // dp[i-2]
long prev1 = s[0] == '*' ? 9 : (s[0] == '0' ? 0 : 1); // dp[i-1]
for (int i = 1; i < n; i++) {
long curr = 0;
// 单个字符解码
if (s[i] == '*') {
curr = (curr + prev1 * 9) % MOD;
} else if (s[i] != '0') {
curr = (curr + prev1) % MOD;
}
// 两个字符一起解码
if (s[i-1] == '1') {
if (s[i] == '*') {
curr = (curr + prev2 * 9) % MOD;
} else {
curr = (curr + prev2) % MOD;
}
} else if (s[i-1] == '2') {
if (s[i] == '*') {
curr = (curr + prev2 * 6) % MOD;
} else if (s[i] <= '6') {
curr = (curr + prev2) % MOD;
}
} else if (s[i-1] == '*') {
if (s[i] == '*') {
curr = (curr + prev2 * 15) % MOD; // 11-19, 21-26
} else if (s[i] <= '6') {
curr = (curr + prev2 * 2) % MOD; // 1x, 2x
} else {
curr = (curr + prev2) % MOD; // 1x only
}
}
prev2 = prev1;
prev1 = curr;
}
return (int)prev1;
}
}
var numDecodings = function(s) {
const MOD = 1000000007;
const n = s.length;
// dp[i] 表示前i个字符的解码方案数
let prev2 = 1; // dp[i-2]
let prev1 = s[0]
复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 动态规划（滚动数组优化） | O(n) | O(1) |
相关题目
. Decode Ways (Medium)