解码方法 II

标签: 字符串 动态规划

难度: 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 <= 105
  • s[i] 是 0 - 9 中的一位数字或字符 '*'

Submission

运行时间: 157 ms

内存: 20.2 MB

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0":
            return 0
        n = len(s)
        dp = [-1] * n
        dp[0] = 1 if s[0]!="*" else 9
        for i in range(1, n):
            if s[i] == "0":
                if s[i-1].isdigit() and s[i-1] not in {"1", "2"}:
                    return 0
                if s[i-1] in {"1", "2"}:
                    dp[i] = dp[i-2] if i>1 else 1
                else:
                    dp[i] = dp[i-2]*2 if i>1 else 2

            elif s[i] in {"1", "2", "3", "4", "5", "6"}:
                if s[i-1] in {"1", "2"}:
                    dp[i] = dp[i-1] + dp[i-2] if i>1 else dp[i-1]+1
                elif s[i-1] == "*":
                    dp[i] = dp[i-1] + dp[i-2]*2 if i>1 else 11
                else:
                    dp[i] = dp[i-1]
            elif s[i] in {"7", "8", "9"}:
                if s[i-1] == "1":
                    dp[i] = dp[i-1] + dp[i-2] if i>1 else dp[i-1]+1
                elif s[i-1] == "*":
                    dp[i] = dp[i-1] + dp[i-2]*1  if i>1 else 10
                else:
                    dp[i] = dp[i-1]
            else:
                if s[i-1] == "1":
                    dp[i] = dp[i-2]*9 + dp[i-1]*9 if i>1 else dp[i-1]*9+9
                elif s[i-1] == "2":
                    dp[i] = dp[i-2]*6 + dp[i-1]*9 if i>1 else dp[i-1]*9+6
                elif s[i-1] == "*":
                    dp[i] = dp[i-1]*9 + dp[i-2]*15 if i>1 else 96
                else:
                    dp[i] = dp[i-1] * 9
            dp[i] = dp[i] % (10**9+7)
            
            # AA~II: 11,12,...,19,21,22,...,29,...,91,...,99    - 81
            # J~Z:  11,...,19,21,...,26                         - 15 
        return dp[-1]

Explain

这个题解使用动态规划的思路来解决解码方法的问题。定义 dp[i] 表示字符串的前 i 个字符有多少种解码方法。对于第 i 个字符，需要根据其是数字还是 '*'，以及前一个字符的情况来更新 dp[i]。具体来说： 1. 如果当前字符是 '0'，那么它只能和前一个字符一起解码，并且前一个字符必须是 '1' 或 '2'，否则无法解码。 2. 如果当前字符是 '1'~'6'，那么它可以单独解码，也可以和前一个字符一起解码（如果前一个字符是 '1' 或 '2'）。 3. 如果当前字符是 '7'~'9'，那么它只能单独解码，或者和前一个字符一起解码（如果前一个字符是 '1'）。 4. 如果当前字符是 '*'，那么它可以表示 '1'~'9' 中的任意数字，需要根据前一个字符是 '1'、'2' 还是其他数字来更新 dp[i]。 最终的答案即为 dp[n-1]，也就是整个字符串的解码方法数目。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0":
            return 0
        n = len(s)
        dp = [-1] * n
        dp[0] = 1 if s[0]!="*" else 9  # 初始化 dp[0]
        for i in range(1, n):
            if s[i] == "0":
                # 处理当前字符为 '0' 的情况
                if s[i-1].isdigit() and s[i-1] not in {"1", "2"}:
                    return 0
                if s[i-1] in {"1", "2"}:
                    dp[i] = dp[i-2] if i>1 else 1
                else:
                    dp[i] = dp[i-2]*2 if i>1 else 2
            elif s[i] in {"1", "2", "3", "4", "5", "6"}:
                # 处理当前字符为 '1'~'6' 的情况
                if s[i-1] in {"1", "2"}:
                    dp[i] = dp[i-1] + dp[i-2] if i>1 else dp[i-1]+1
                elif s[i-1] == "*":
                    dp[i] = dp[i-1] + dp[i-2]*2 if i>1 else 11
                else:
                    dp[i] = dp[i-1]
            elif s[i] in {"7", "8", "9"}:
                # 处理当前字符为 '7'~'9' 的情况
                if s[i-1] == "1":
                    dp[i] = dp[i-1] + dp[i-2] if i>1 else dp[i-1]+1
                elif s[i-1] == "*":
                    dp[i] = dp[i-1] + dp[i-2]*1  if i>1 else 10
                else:
                    dp[i] = dp[i-1]
            else:
                # 处理当前字符为 '*' 的情况
                if s[i-1] == "1":
                    dp[i] = dp[i-2]*9 + dp[i-1]*9 if i>1 else dp[i-1]*9+9
                elif s[i-1] == "2":
                    dp[i] = dp[i-2]*6 + dp[i-1]*9 if i>1 else dp[i-1]*9+6
                elif s[i-1] == "*":
                    dp[i] = dp[i-1]*9 + dp[i-2]*15 if i>1 else 96
                else:
                    dp[i] = dp[i-1] * 9
            dp[i] = dp[i] % (10**9+7)  # 取模避免溢出
        return dp[-1]

Explore

在计算机科学中，经常使用模运算来防止数值溢出，尤其是在涉及大数运算的情况。10^9+7 是一个常用的大质数，使用它作为模数有几个好处：1) 它足够大，可以保证大多数计算不会产生溢出；2) 它是质数，这有助于在某些数学运算中保持良好的分布性；3) 它适合用于模算术，因为具有良好的性能和分布特性。使用此模数帮助我们在不丢失数据精度的前提下，处理大规模数据。

当当前字符是'0'而前一个字符是'*'时，'*'可以代表'1'或'2'（因为只有'10'和'20'是有效的编码）。因此，如果 s[i-1] 是 '*'，则 '*' 可以解码为 '1' 或 '2'，使得组合为 '10' 或 '20'。因此，dp[i] 应该等于 dp[i-2] 的值（如果 i>1），如果 i=1，则 dp[i] 应该为 2（即有两种情况：'10' 和 '20'）。

当当前字符为'*'时，它可以代表从'1'到'9'的任意数字。如果前一个字符是'1'，那么 '*' 可以形成与 '1' 的组合，即 '11' 到 '19'，共9种情况。如果前一个字符是'2'，'*' 可以形成 '21' 到 '26'，共6种情况（因为只有'21'到'26'是有效的编码）。因此，当 s[i-1] 是 '1' 或 '2' 时，dp[i] 的更新规则应分别添加 dp[i-2]*9（如果前一个字符是 '1'）和 dp[i-2]*6（如果前一个字符是 '2'），来反映这些额外的组合解码方式。

当当前字符在'1'~'6'范围内时，可以单独解码。如果前一个字符是'*'，则 '*' 可以代表 '1' 或 '2'。这意味着，除了可以单独解码当前字符外，还可以与前一个字符形成有效的双字符编码（例如，'*1'， '*2'，'*3'，'*4'，'*5'，'*6'，其中'*'可以是'1'或'2'）。因此，对于每个这样的双字符组合，都有一种额外的解码方式，即 dp[i-2]。因此，dp[i] 更新为 dp[i-1] 加上 dp[i-2] 的两倍，反映了这两种可能性（'*'代表'1'和'*'代表'2'）。