No.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 ，由数字和 '*' 字符组成，返回解码该字符串的方法数目。

由于答案数目可能非常大，返回对 10⁹ + 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⁵
s[i] 是 0 - 9 中的一位数字或字符 '*'

思路分析

这一题考察的主要就是思路严密。
通过题目所给信息不难判断这是一个一维的动态规划。
思路也是非常动态规划，dp[i]为使用了s的前i个字符所有的方案数。

如果s[i] 不是 '0'，那么就说明可以单独作为一个方案。也就是 dp[i + 1] += dp[i]
如果s[i - 1]和s[i]可以组成大于等于10（此处应为大坑，因为不能出现"01"）且小于等于26的数字，那么我们就认为可以将这两位数作为一个方案。dp[i + 1] += dp[i - 1]

思路非常简单，但是实现比较复杂，是因为我们总是会忽略各种各样的情况，比如"*"只能代表1到9，"01"不能作为合法的数之类的。

主要的思路就是分开来写，对于s[i]和s[i-1]是不是"*"分四种情况讨论，这样就不会漏了。

C++代码

using ll = int64_t;
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        ll dp[n + 1];
        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '*') dp[i + 1] += dp[i] * 9;
            else if (s[i] != '0') dp[i + 1] += dp[i];
            if (i > 0) {
// cout << "Good";
                if (s[i - 1] == '*' && s[i] != '*'){
                    if (s[i] <= '6') dp[i + 1] += 2 * dp[i - 1];
                    else dp[i + 1] += dp[i - 1];
                } else if (s[i - 1] == '*' && s[i] == '*') {
                    // cout << "Good";
                    dp[i + 1] += dp[i - 1] * 15;
                } else if (s[i - 1] != '*' && s[i] == '*') {
                    if (s[i - 1] == '1') dp[i + 1] += dp[i - 1] * 9;
                    else if (s[i - 1] == '2') dp[i + 1] += dp[i - 1] * 6;
                } else {
                    if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6'))
                        dp[i + 1] += dp[i - 1];
                }
            }
            dp[i + 1] %= ll(1e9 + 7);
        }
        return dp[n];
    }
};

LeetCode Solution - 力扣题解

No.639 解码方法 II

思路分析

C++代码