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:动态规划 #
这道题是「 91. 解码方法 - 力扣」的升级版,其思路是相似的,只不过本题的状态转移方程的条件和公式不太容易想全。
1. 划分阶段 #
按照字符串的结尾位置进行阶段划分。
2. 定义状态 #
定义状态 dp[i]
表示为:字符串 s
前 i
个字符构成的字符串可能构成的翻译方案数。
3. 状态转移方程 #
dp[i]
的来源有两种情况:
-
使用了一个字符,对
s[i]
进行翻译:- 如果
s[i] == '*'
,则s[i]
可以视作区间[1, 9]
上的任意一个数字,可以被翻译为A
~I
。此时当前位置上的方案数为9
,即dp[i] = dp[i - 1] * 9
。 - 如果
s[i] == '0'
,则无法被翻译,此时当前位置上的方案数为0
,即dp[i] = dp[i - 1] * 0
。 - 如果是其他情况(即
s[i]
是区间[1, 9]
上某一个数字),可以被翻译为A
~I
对应位置上的某个字母。此时当前位置上的方案数为1
,即dp[i] = dp[i - 1] * 1
。
- 如果
-
使用了两个字符,对
s[i - 1]
和s[i]
进行翻译:-
如果
s[i - 1] == '*'
并且s[i] == '*'
,则s[i]
可以视作区间[11, 19]
或者[21, 26]
上的任意一个数字。此时当前位置上的方案数为15
,即dp[i] = dp[i - 2] * 15
。 -
如果
s[i - 1] == '*'
并且s[i] != '*'
,则:- 如果
s[i]
在区间[1, 6]
内,s[i - 1]
可以选择1
或2
。此时当前位置上的方案数为2
,即dp[i] = dp[i - 2] * 2
。 - 如果
s[i]
不在区间[1, 6]
内,s[i - 1]
只能选择1
。此时当前位置上的方案数为1
,即dp[i] = dp[i - 2] * 1
。
- 如果
-
如果
s[i - 1] == '1'
并且s[i] == '*'
,s[i]
可以视作区间[1, 9]
上任意一个数字。此时当前位置上的方案数为9
,即dp[i] = dp[i - 2] * 9
。 -
如果
s[i - 1] == '1'
并且s[i] != '*'
,s[i]
可以视作区间[1, 9]
上的某一个数字。此时当前位置上的方案数为1
,即dp[i] = dp[i - 2] * 1
。 -
如果
s[i - 1] == '2'
并且s[i] == '*'
,s[i]
可以视作区间[1, 6]
上任意一个数字。此时当前位置上的方案数为6
,即dp[i] = dp[i - 2] * 6
。 -
如果
s[i - 1] == '2'
并且s[i] != '*'
,则:- 如果
s[i]
在区间[1, 6]
内,此时当前位置上的方案数为1
,即dp[i] = dp[i - 2] * 1
。 - 如果
s[i]
不在区间[1, 6]
内,此时当前位置上的方案数为0
,即dp[i] = dp[i - 2] * 0
。
- 如果
-
其他情况下(即
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:复杂度分析 #
- 时间复杂度:$O(n)$。一重循环遍历的时间复杂度是 $O(n)$。
- 空间复杂度:$O(n)$。用到了一维数组保存状态,所以总体空间复杂度为 $O(n)$。