639-解码方法 II(Decode Ways II)
发表于：2021-12-03 | 分类： 困难
字数统计: 3.5k | 阅读时长: 17分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/decode-ways-ii

英文原文

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

  • "AAJF" with the grouping (1 1 10 6)
  • "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

In addition to the mapping above, an encoded message may contain the '*' character, which can represent any digit from '1' to '9' ('0' is excluded). For example, the encoded message "1*" may represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19". Decoding "1*" is equivalent to decoding any of the encoded messages it can represent.

Given a string s consisting of digits and '*' characters, return the number of ways to decode it.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: s = "*"
Output: 9
Explanation: The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9".
Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively.
Hence, there are a total of 9 ways to decode "*".

Example 2:

Input: s = "1*"
Output: 18
Explanation: The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19".
Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K").
Hence, there are a total of 9 * 2 = 18 ways to decode "1*".

Example 3:

Input: s = "2*"
Output: 15
Explanation: The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29".
"21", "22", "23", "24", "25", and "26" have 2 ways of being decoded, but "27", "28", and "29" only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode "2*".

 

Constraints:

  • 1 <= s.length <= 105
  • s[i] is a digit or '*'.

中文题目

一条包含字母 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 中的一位数字或字符 '*'

通过代码

高赞题解

分情况讨论 DP

这是一道普通的线性 DP 题（之所以说普通，是因为状态定义比较容易想到），也是 （题解）91. 解码方法 的进阶题。

我们称一个解码内容为一个 item。

定义 $f[i]$ 为考虑以 $s[i]$ 为结尾的字符串，共有多少种解码方案。

那么最终答案为 $f[n - 1]$，同时我们有显而易见的起始状态 f[0] = s[0] == '*' ? 9 : (s[0] != '0' ? 1 : 0).

不失一般性考虑 $f[i]$ 该如何转移，$s[i]$ 要么是 *，要么是数字，对应一个分情况讨论过程：

  • 当 $s[i]$ 为 *：此时考虑 $s[i]$ 是单独作为一个 item，还是与上一个字符共同作为一个 item:

    • $s[i]$ 单独作为一个 item：由于 * 可以代指数字 1-9，因此有 $f[i] = f[i - 1] * 9$；
    • $s[i]$ 与上一个字符共同作为一个 item：此时需要对上一个字符 $s[j]$ 进行讨论：
      • $s[j]$ 为数字 1：此时 $s[i]$ 可以代指 1-9，对应了 item 为 11-19 这 $9$ 种情况，此时有 $f[i] = f[i - 2] * 9$（如果 $f[i - 2]$ 取不到，则使用 $1$ 代指，下面同理）；
      • $s[j]$ 为数字 2：此时 $s[i]$ 可以代指 1-6，对应了 item 为 21-26 这 $6$ 种情况，此时有 $f[i] = f[i - 2] * 6$；
      • $s[j]$ 为字符 *：此时两个 * 对应了合法方案为 $11-19$ 和 $21-26$ 共 $15$ 种方案，此时有 $f[i] = f[i - 2] * 15$；

  • 当 $s[i]$ 为数字：此时可以从「前一字符 $s[j]$ 为何种字符」和「当前 $s[i]$ 是否为 $0$」出发进行讨论:

    • $s[j]$ 为字符 *，根据当前 $s[i]$ 是否为 $0$ 讨论：
      • $s[i]$ 为数字 $0$：此时 $s[i]$ 无法独自作为一个 item，只能与 $s[j]$ 组合，对应了 $10$ 和 $20$ 两种情况，此时有 $f[i] = f[i - 2] * 2$；
      • $s[i]$ 为数字 1-9，此时首先有 $s[i]$ 可以作为一个独立 item 的情况，即有 $f[i] = f[i - 1]$，然后对 $s[i]$ 的数值大小进一步分情况讨论：
        • $s[i]$ 为数字 1-6，此时 $s[j]$ 可以代指 $1$ 和 $2$，对应了方案 $1x$ 和 $2x$，此时有 $f[i] = f[i - 2] * 2$；
        • $s[i]$ 为数字 7-9，此时 $s[j]$ 可以代指 $1$，对应方案 $1x$，此时有 $f[i] = f[i - 2]$；
    • $s[j]$ 为数字类型，此时从「当前 $s[i]$ 是否为 $0$」出发进行讨论：
      • $s[i]$ 为数字 $0$：此时 $s[j]$ 只有为 $1$ 和 $2$ 时，才是合法方案，则有 $f[i] = f[i - 2]$；
      • $s[i]$ 为数字 1-9：此时首先有 $s[i]$ 可以作为一个独立 item 的情况，即有 $f[i] = f[i - 1]$，然后再考虑能够与 $s[j]$ 组成合法 item 的情况：
        • $s[j]$ 为数值 $1$：此时有 $f[i] = f[i - 2]$；
        • $s[j]$ 为数值 $2$，且 $s[i]$ 为数值 1-6：此时有 $f[i] = f[i - 2]$。

由于是求方案数，因此最终的 $f[i]$ 为上述所有的合法的分情况讨论的累加值，并对 $1e9+ 7$ 取模。

一些细节：实现上了避免大量对 $f[i - 2]$ 是否可以取得的讨论，我们可以对 s 前追加一个空格作为哨兵（无须真正插入），以简化代码，同时由于 $f[i]$ 只依赖于 $f[i - 1]$ 和 $f[i - 1]$，可以使用「滚动数组」的形式进行空间空间优化（见 $P2$）。

另外，对于「滚动数组」的空间优化方式，还需要说明两点：转移前先使用变量保存 (i-1)%3 和 (i-2)%3 的计算结果，防止大量的重复计算；不能再偷懒使用 toCharArray，只能使用 charAt，因为 Java 为了遵循字符串不变的原则，会在调用 toCharArray 时返回新数组，这样复杂度就还是 $O(n)$ 的。
诸如此类的「滚动数组」优化方式，最早在 这里 讲过。

代码：

[]
class Solution {
    int mod = (int)1e9+7;
    public int numDecodings(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        long[] f = new long[n];
        f[0] = cs[0] == '*' ? 9 : (cs[0] != '0' ? 1 : 0);
        for (int i = 1; i < n; i++) {
            char c = cs[i], prev = cs[i - 1];
            if (c == '*') {
                // cs[i] 单独作为一个 item
                f[i] += f[i - 1] * 9;
                // cs[i] 与前一个字符共同作为一个 item
                if (prev == '*') {
                    // 11 - 19 & 21 - 26
                    f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 15;
                } else {
                    int u = (int)(prev - '0');
                    if (u == 1) {
                        f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 9;
                    } else if (u == 2) {
                        f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 6;
                    }
                }
            } else {
                int t = (int)(c - '0');
                if (prev == '*') {
                    if (t == 0) {
                        f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 2;
                    } else {
                        // cs[i] 单独作为一个 item
                        f[i] += f[i - 1];
                        // cs[i] 与前一个字符共同作为一个 item
                        if (t <= 6) {
                            f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 2;
                        } else {
                            f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                        }
                    }
                } else {
                    int u = (int)(prev - '0');
                    if (t == 0) {
                        if (u == 1 || u == 2) {
                            f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                        }
                    } else {
                        // cs[i] 单独作为一个 item
                        f[i] += (f[i - 1]);
                        // cs[i] 与前一个字符共同作为一个 item
                        if (u == 1) {
                            f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                        } else if (u == 2 && t <= 6) {
                            f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                        }
                    }
                }
            }
            f[i] %= mod;
        }
        return (int)(f[n - 1]);
    }
}
[]
class Solution {
    int mod = (int)1e9+7;
    public int numDecodings(String s) {
        int n = s.length() + 1;
        long[] f = new long[3];
        f[0] = 1;
        f[1] = s.charAt(0) == '*' ? 9 : (s.charAt(0) != '0' ? 1 : 0);
        for (int i = 2; i < n; i++) {
            char c = s.charAt(i - 1), prev = s.charAt(i - 2);
            int p1 = (i - 1) % 3, p2 = (i - 2) % 3;
            long cnt = 0;
            if (c == '*') {
                // cs[i] 单独作为一个 item
                cnt += f[p1] * 9;
                // cs[i] 与前一个字符共同作为一个 item
                if (prev == '*') {
                    cnt += f[p2] * 15;
                } else {
                    int u = (int)(prev - '0');
                    if (u == 1) cnt += f[p2] * 9;
                    else if (u == 2) cnt += f[p2] * 6;
                }
            } else {
                int t = (int)(c - '0');
                if (prev == '*') {
                    if (t == 0) {
                        cnt += f[p2]* 2;
                    } else {
                        // cs[i] 单独作为一个 item
                        cnt += f[p1];
                        // cs[i] 与前一个字符共同作为一个 item
                        if (t <= 6) cnt += f[p2] * 2;
                        else cnt += f[p2];
                    }
                } else {
                    int u = (int)(prev - '0');
                    if (t == 0) {
                        if (u == 1 || u == 2) cnt += f[p2];
                    } else {
                        // cs[i] 单独作为一个 item
                        cnt += f[p1];
                        // cs[i] 与前一个字符共同作为一个 item
                        if (u == 1) cnt += f[p2];
                        else if (u == 2 && t <= 6) cnt += f[p2];
                    }
                }
            }
            f[i % 3] = cnt % mod;
        }
        return (int)(f[(n - 1) % 3]);
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：使用「滚动数组」进行优化，复杂度为 $O(1)$，否则为 $O(n)$

枚举 DP

上述解法之所以复杂，是因为不仅仅要对当前字符 $s[i]$ 分情况讨论，还需要对上一个字符 $s[j]$ 分情况讨论。

事实上，我们可以利用解码对象只有 A-Z 来进行枚举。

在从前往后处理字符串 s 时，枚举 $s[i]$ 参与构成的解码内容 item 是字母 A-Z 中哪一个，从而将分情况讨论转变成对应位的字符对比。

代码：

[]
class Solution {
    int mod = (int)1e9+7;
    public int numDecodings(String s) {
        int n = s.length();
        long[] f = new long[3];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            char c = s.charAt(i - 1);
            int t = c - '0';
            long cnt = 0;
            int p1 = (i - 1) % 3, p2 = (i - 2) % 3;
            // 枚举组成什么 item（A -> 1; B -> 2 ...）
            for (int item = 1; item <= 26; item++) { 
                if (item < 10) { // 该 item 由一个字符组成
                    if (c == '*' || t == item) cnt += f[p1];
                } else { // 该 item 由两个字符组成
                    if (i - 2 < 0) break;
                    char prev = s.charAt(i - 2);
                    int u = prev - '0';
                    int a = item / 10, b = item % 10;
                    if ((prev == '*' || u == a) && (t == b || (c == '*' && b != 0))) cnt += f[p2];
                }
            }
            f[i % 3] = cnt % mod;
        }
        return (int)(f[n % 3]);
    }
}
  • 时间复杂度：$O(n * C)$，其中 $C$ 为解码内容字符集大小，固定为 $26$
  • 空间复杂度：$O(1)$

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数 提交次数 AC比率
20384 54120 37.7%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
解码方法 中等
字符串 动态规划
上一篇:
638-大礼包(Shopping Offers)
下一篇:
640-求解方程(Solve the Equation)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo