今天是我坚持写题解的第 54 天！
题目描述（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
，由数字和 '*'
字符组成，返回 解码 该字符串的方法 数目 。
由于答案数目可能非常大，返回对 10^9 + 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 中的一位数字或字符 '*'
链接：https://leetcode-cn.com/problems/decode-ways-ii
方法一、记忆化搜索
今天这道题我们先考虑暴力求解，从头开始遍历，每遍历到一个字符，它有两种解码方案，一种是只解码当前这一个字符，另一种是解码当前及其后面的共两个字符，两种方案相加就是当前字符的解码方案数，当然，这里还要加上递归的逻辑，解码当前字符之后需要继续解码后面的字符，不同字符的解码方案数之间是组合的关系，即相乘。
另外，因为每一次递归有两种选择，所以，对于某个确定的 i
，它可能会被多次遍历到，因此，我们需要加上记忆化数组缓存下来每个位置最终的方案数。
请看代码：
class Solution {
int MOD = 1000000007;
public int numDecodings(String s) {
// 1. 只解码当前一个字符，分成 0、1~9、* 来分别讨论
// 2. 解码两个字符，分成 **、*X、X*、XX 来分别讨论
int n = s.length();
long[] memo = new long[n];
// 初始化为-1，因为0表示没有方案数
Arrays.fill(memo, -1);
return (int) dfs(s, 0, memo);
}
private long dfs(String s, int i, long[] memo) {
if (i == s.length()) {
return 1;
}
if (i > s.length()) {
return 0;
}
if (memo[i] != -1) {
return memo[i];
}
long ans = (decodeOneChar(s.charAt(i)) * dfs(s, i + 1, memo) + (i + 1 >= s.length() ? 0 :decodeTwoChars(s.charAt(i), s.charAt(i + 1)) * dfs(s, i + 2, memo))) % MOD;
memo[i] = ans;
return ans;
}
private int decodeOneChar(char c) {
if (c == '0') {
// 0 不能单独解码
return 0;
}
if (c == '*') {
// * 可选 1~9 任意一个数解码
return 9;
}
// 确定的数字与前一位的解码方案数保持一致
return 1;
}
private int decodeTwoChars(char c1, char c2) {
if (c1 == '*' && c2 == '*') {
// 两个都是 * 号，有 11~19，21~26 共15种选择
return 15;
}
if (c1 == '*') {
// 如果当前位为 0~6，* 可选1和2
if (c2 <= '6') {
return 2;
}
// 如果当前位为 7~9，*只能选择1
return 1;
}
if (c2 == '*') {
// 如果前一位为1，则有 1~9 共9种选择
if (c1 == '1') {
return 9;
}
// 如果前一位为2，则有 1~6 共6种选择
if (c1 == '2') {
return 6;
}
// 如果前一位为 0 或 3~9，则不行
return 0;
}
// 两个字符的和是 10 ~ 26 才能够组合在一起，否则不行
int twoSum = (c1 - '0') * 10 + (c2 - '0');
if (twoSum >= 10 && twoSum <= 26) {
return 1;
}
return 0;
}
public static void main(String[] args) {
System.out.println(new Solution().numDecodings("104"));
}
}复制
时间复杂度：，因为有记忆化数组，所以，每个位置最多只会计算一遍。 空间复杂度：。
运行结果如下：
方法二、动态规划
有了记忆化搜索我们可以考虑使用动态规划来求解，只需要把 memo
数组转成 dp
数组即可，动态规划的定义如下：
状态定义： dp[i]
表示前i
个字符的解码方案数。状态转移： dp[i] = x * dp[i - 1] + y * dp[i - 2]
，x
表示解码当前一个字符的方案数，y
表示解码当前及上一个共两个字符的方案数，至于怎么解码一个字符和两个字符，按照题目的意思来模拟就可以了。初始值： dp[0] = 1
，表示空字符串时的解码方案数，显然为1。返回值： dp[n]
。
也可以定义为：以
s[i]
结尾的字符的解码方案数，稍微麻烦一丢丢
请看代码，加了详细注释：
class Solution {
int MOD = 1000000007;
public int numDecodings(String s) {
// dp[i]表示前i个字符的解码方案数
// 1. 只解码当前一个字符，分成 0、1~9、* 来分别讨论
// 2. 解码两个字符，分成 **、*X、X*、XX 来分别讨论
int n = s.length();
long[] dp = new long[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = (decodeOneChar(s.charAt(i - 1)) * dp[i - 1] + (i - 2 < 0 ? 0 : decodeTwoChars(s.charAt(i - 2), s.charAt(i - 1)) * dp[i - 2])) % MOD;
}
return (int) dp[n];
}
private int decodeOneChar(char c) {
if (c == '0') {
// 0 不能单独解码
return 0;
}
if (c == '*') {
// * 可选 1~9 任意一个数解码
return 9;
}
// 确定的数字与前一位的解码方案数保持一致
return 1;
}
private int decodeTwoChars(char c1, char c2) {
if (c1 == '*' && c2 == '*') {
// 两个都是 * 号，有 11~19，21~26 共15种选择
return 15;
}
if (c1 == '*') {
// 如果当前位为 0~6，* 可选1和2
if (c2 <= '6') {
return 2;
}
// 如果当前位为 7~9，*只能选择1
return 1;
}
if (c2 == '*') {
// 如果前一位为1，则有 1~9 共9种选择
if (c1 == '1') {
return 9;
}
// 如果前一位为2，则有 1~6 共6种选择
if (c1 == '2') {
return 6;
}
// 如果前一位为 0 或 3~9，则不行
return 0;
}
// 两个字符的和是 10 ~ 26 才能够组合在一起，否则不行
int twoSum = (c1 - '0') * 10 + (c2 - '0');
if (twoSum >= 10 && twoSum <= 26) {
return 1;
}
return 0;
}
}复制
时间复杂度：。 空间复杂度：。
运行结果如下：
方法三、动态规划 + 优化
方法一可以看到 dp[i]
只与其前两项有关，所以，我们可以声明三个变量轮动代替 dp
数组。
请看代码：
class Solution {
int MOD = 1000000007;
public int numDecodings(String s) {
// dp[i]表示前i个字符的解码方案数
// 1. 只解码当前一个字符，分成 0、1~9、* 来分别讨论
// 2. 解码两个字符，分成 **、*X、X*、XX 来分别讨论
int n = s.length();
long a = 0, b = 1, c = 0;
for (int i = 1; i <= n; i++) {
c = (decodeOneChar(s.charAt(i - 1)) * b + (i - 2 < 0 ? 0 : decodeTwoChars(s.charAt(i - 2), s.charAt(i - 1)) * a)) % MOD;
a = b;
b = c;
}
return (int) c;
}
private int decodeOneChar(char c) {
if (c == '0') {
// 0 不能单独解码
return 0;
}
if (c == '*') {
// * 可选 1~9 任意一个数解码
return 9;
}
// 确定的数字与前一位的解码方案数保持一致
return 1;
}
private int decodeTwoChars(char c1, char c2) {
if (c1 == '*' && c2 == '*') {
// 两个都是 * 号，有 11~19，21~26 共15种选择
return 15;
}
if (c1 == '*') {
// 如果当前位为 0~6，* 可选1和2
if (c2 <= '6') {
return 2;
}
// 如果当前位为 7~9，*只能选择1
return 1;
}
if (c2 == '*') {
// 如果前一位为1，则有 1~9 共9种选择
if (c1 == '1') {
return 9;
}
// 如果前一位为2，则有 1~6 共6种选择
if (c1 == '2') {
return 6;
}
// 如果前一位为 0 或 3~9，则不行
return 0;
}
// 两个字符的和是 10 ~ 26 才能够组合在一起，否则不行
int twoSum = (c1 - '0') * 10 + (c2 - '0');
if (twoSum >= 10 && twoSum <= 26) {
return 1;
}
return 0;
}
}复制
时间复杂度：。 空间复杂度：。
运行结果如下：
最后
如果对你有帮助，请点个赞吧，谢谢^^
也可以关注我，每日分享题解，一起刷题，一起拿全家桶。
