题目描述

一条包含字母 A-Z 的消息通过以下的方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

除了上述的条件以外，现在加密字符串可以包含字符 * 了，字符 * 可以被当做 1 到 9 当中的任意一个数字。

给定一条包含数字和字符 * 的加密信息，请确定解码方法的总数。

同时，由于结果值可能会相当的大，所以你应当对 $10^9 + 7$ 取模。（翻译者标注：此处取模主要是为了防止溢出）

样例

输入: "*"
输出: 9
解释: 加密的信息可以被解密为: "A", "B", "C", "D", "E", "F", "G", "H", "I"。

输入: "1*"
输出: 9 + 9 = 18（翻译者标注：这里 1* 可以分解为 1,* 或者当做 1* 整体来处理，所以结果是 9 + 9 = 18）。

注意

• 输入的字符串长度范围是 [1, $10^5$]。
• 输入的字符串只会包含字符 * 和 数字 0 - 9。

算法

(动态规划) $O(n)$

1. 设计状态 $f(i)$ 表示前 $i$ 个字符组成的字符串的解码总数。
2. 初始状态 $f(0)=1$；这里需要再初始化 $f(1)$，其中若第一个字符为 *，则 $f(1) = 9$；若第一个字符为非零数字，则 $f(1) = 1$；若第一个字符为零，则直接返回 0。
3. 转移时需要分多种情况讨论，具体在代码中阐释。
4. 最后答案为 $f(n)$。

时间复杂度

• 状态数为 $O(n)$，常数个转移，故总时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int numDecodings(string s) {
        int n = s.length(), mod = 1000000007;
        vector<int> f(n + 1, 0);

        f[0] = 1;
        if (s[0] == '*')
            f[1] = 9;
        else if (s[0] == '0')
            return 0;
        else
            f[1] = 1;

        for (int i = 2; i <= n; i++) {
            char c = s[i - 1], lc = s[i - 2];
            // 取出当前字符和上一个字符
            if (c == '*') { // 当前字符为 *
                f[i] = (f[i] + f[i - 1] * 9ll) % mod;
                // 可以单独视为一个数位，总共有 9 种解码方式，根据乘法原理和加法原理累计。
                if (lc == '*') // 若上一个数位也为 *，则两个数位可以合并，共有 15 种可能（因为 * 不能视为 0）。
                    f[i] = (f[i] + f[i - 2] * 15ll) % mod;
                else if (lc == '1') // 若上一个数位为 1，则两个数位可以合并，共有 9 种可能。
                    f[i] = (f[i] + f[i - 2] * 9ll) % mod;
                else if (lc == '2') // 若上一个数位为 1，则两个数位可以合并，共有 6 种可能。
                    f[i] = (f[i] + f[i - 2] * 6ll) % mod;
            }
            else if (c == '0') { // 当前字符为 0，只能考虑和上一位合并。
                if (lc == '*') // 若上一个数位为 *，则有 2 种可能。
                    f[i] = (f[i] + f[i - 2] * 2ll) % mod;
                else if (lc == '1' || lc == '2') // 若上一个数位为 1 或 2，则有 1 种可能。
                    f[i] = (f[i] + f[i - 2]) % mod;
            }
            else if (c >= '1' && c <= '6') { // 当前数位为 1 到 6。
                f[i] = (f[i] + f[i - 1]) % mod;
                // 单独视为一个数位。
                if (lc == '*') // 和上一个 * 合并，2 种可能。
                    f[i] = (f[i] + f[i - 2] * 2ll) % mod;
                else if (lc == '1' || lc == '2') // 和上一个 1 或 2 合并，仅有 1 种可能。
                    f[i] = (f[i] + f[i - 2]) % mod;
            }
            else { // 当前数位为 7 到 9。
                f[i] = (f[i] + f[i - 1]) % mod;
                // 单独视为一个数位。
                if (lc == '*' || lc == '1') // 和上一个 * 或 1 合并，仅有 1 种可能。
                    f[i] = (f[i] + f[i - 2]) % mod;
            }
            // 如果发现当前位答案数量和上一位答案数量都是 0，则显然后续无需再考虑，也都是 0。
            if (f[i] == 0 && f[i - 1] == 0)
                return 0;
        }
        return f[n];
    }
};