0639. 解码方法 II #

标签：字符串、动态规划
难度：困难

题目大意 #

描述：给定一个包含数字和字符 '*' 的字符串 s。该字符串已经按照下面的映射关系进行了编码：

A 映射为 1。
B 映射为 2。
…
Z 映射为 26。

除了上述映射方法，字符串 s 中可能包含字符 '*'，可以表示 1 ~ 9 的任一数字（不包括 0）。例如字符串 "1*" 可以表示为 "11"、"12"、…、"18"、"19" 中的任何一个编码。

基于上述映射的方法，现在对字符串 s 进行「解码」。即从数字到字母进行反向映射。比如 "11106" 可以映射为：

"AAJF"，将消息分组为 (1 1 10 6)。
"KJF"，将消息分组为 (11 10 6)。

要求：计算出共有多少种可能的解码方案。

说明：

$1 \le s.length \le 100$。
s 只包含数字，并且可能包含前导零。
题目数据保证答案肯定是一个 32 位的整数。

1
2
3


输入：s = "*"
输出：9
解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。因此，"*" 总共有 9 种解码方法。

解题思路 #

思路 1：动态规划 #

这道题是「 91. 解码方法 - 力扣」的升级版，其思路是相似的，只不过本题的状态转移方程的条件和公式不太容易想全。

1. 划分阶段 #

按照字符串的结尾位置进行阶段划分。

2. 定义状态 #

定义状态 dp[i] 表示为：字符串 s 前 i 个字符构成的字符串可能构成的翻译方案数。

3. 状态转移方程 #

dp[i] 的来源有两种情况：

使用了一个字符，对 s[i] 进行翻译：
1. 如果 s[i] == '*'，则 s[i] 可以视作区间 [1, 9] 上的任意一个数字，可以被翻译为 A ~ I。此时当前位置上的方案数为 9，即 dp[i] = dp[i - 1] * 9。
2. 如果 s[i] == '0'，则无法被翻译，此时当前位置上的方案数为 0，即 dp[i] = dp[i - 1] * 0。
3. 如果是其他情况（即 s[i] 是区间 [1, 9] 上某一个数字），可以被翻译为 A ~ I 对应位置上的某个字母。此时当前位置上的方案数为 1，即 dp[i] = dp[i - 1] * 1。
使用了两个字符，对 s[i - 1] 和 s[i] 进行翻译：
1. 如果 s[i - 1] == '*' 并且 s[i] == '*'，则 s[i] 可以视作区间 [11, 19] 或者 [21, 26] 上的任意一个数字。此时当前位置上的方案数为 15，即 dp[i] = dp[i - 2] * 15。
2. 如果 s[i - 1] == '*' 并且 s[i] != '*'，则：
  1. 如果 s[i] 在区间 [1, 6] 内，s[i - 1] 可以选择 1 或 2。此时当前位置上的方案数为 2，即 dp[i] = dp[i - 2] * 2。
  2. 如果 s[i] 不在区间 [1, 6] 内，s[i - 1] 只能选择 1。此时当前位置上的方案数为 1，即 dp[i] = dp[i - 2] * 1。
3. 如果 s[i - 1] == '1' 并且 s[i] == '*'，s[i] 可以视作区间 [1, 9] 上任意一个数字。此时当前位置上的方案数为 9，即 dp[i] = dp[i - 2] * 9。
4. 如果 s[i - 1] == '1' 并且 s[i] != '*'，s[i] 可以视作区间 [1, 9] 上的某一个数字。此时当前位置上的方案数为 1，即 dp[i] = dp[i - 2] * 1。
5. 如果 s[i - 1] == '2' 并且 s[i] == '*'，s[i] 可以视作区间 [1, 6] 上任意一个数字。此时当前位置上的方案数为 6，即 dp[i] = dp[i - 2] * 6。
6. 如果 s[i - 1] == '2' 并且 s[i] != '*'，则：
  1. 如果 s[i] 在区间 [1, 6] 内，此时当前位置上的方案数为 1，即 dp[i] = dp[i - 2] * 1。
  2. 如果 s[i] 不在区间 [1, 6] 内，此时当前位置上的方案数为 0，即 dp[i] = dp[i - 2] * 0。
7. 其他情况下（即 s[i - 1] 在区间 [3, 9] 内），则无法被翻译，此时当前位置上的方案数为 0，即 dp[i] = dp[i - 2] * 0。

在进行转移的时候，需要将使用一个字符的翻译方案数与使用两个字符的翻译方案数进行相加。同时还要注意对 $10^9 + 7$ 的取余。

这里我们可以单独写两个方法 ，分别来表示「单个字符 s[i]的翻译方案数」和「两个字符s[i - 1]和s[i]` 的翻译方案数」，这样代码逻辑会更加清晰。

4. 初始条件 #

字符串为空时，只有一个翻译方案，翻译为空字符串，即 dp[0] = 1。
字符串只有一个字符时，单个字符 s[i] 的翻译方案数为转移条件的第一种求法，即dp[1] = self.parse1(s[0])。

5. 最终结果 #

根据我们之前定义的状态，dp[i] 表示为：字符串 s 前 i 个字符构成的字符串可能构成的翻译方案数。则最终结果为 dp[size]，size 为字符串长度。

思路 1：动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution:
    def parse1(self, ch):
        if ch == '*':
            return 9
        if ch == '0':
            return 0
        return 1

    def parse2(self, ch1, ch2):
        if ch1 == '*' and ch2 == '*':
            return 15
        if ch1 == '*' and ch2 != '*':
            return 2 if ch2 <= '6' else 1

        if ch1 == '1' and ch2 == '*':
            return 9
        if ch1 == '1' and ch2 != '*':
            return 1

        if ch1 == '2' and ch2 == '*':
            return 6
        if ch1 == '2' and ch2 != '*':
            return 1 if ch2 <= '6' else 0

        return 0

    def numDecodings(self, s: str) -> int:
        mod = 10 ** 9 + 7
        size = len(s)

        dp = [0 for _ in range(size + 1)]
        dp[0] = 1
        dp[1] = self.parse1(s[0])

        for i in range(2, size + 1):
            dp[i] += dp[i - 1] * self.parse1(s[i - 1])
            dp[i] += dp[i - 2] * self.parse2(s[i - 2], s[i - 1])
            dp[i] %= mod
        
        return dp[size]

思路 1：复杂度分析 #

时间复杂度：$O(n)$。一重循环遍历的时间复杂度是 $O(n)$。
空间复杂度：$O(n)$。用到了一维数组保存状态，所以总体空间复杂度为 $O(n)$。