0010. 正则表达式匹配 #
- 标签:递归、字符串、动态规划
- 难度:困难
题目大意 #
描述:给定一个字符串 s
和一个字符模式串 p
。
要求:实现一个支持 '.'
和 '*'
的正则表达式匹配。两个字符串完全匹配才算匹配成功。如果匹配成功,则返回 True
,否则返回 False
。
'.'
匹配任意单个字符。'*'
匹配零个或多个前面的那一个元素。
说明:
- $1 \le s.length \le 20$。
- $1 \le p.length \le 30$。
s
只包含从a
~z
的小写字母。p
只包含从a
~z
的小写字母,以及字符.
和*
。- 保证每次出现字符
*
时,前面都匹配到有效的字符。
示例:
|
|
解题思路 #
思路 1:动态规划 #
1. 划分阶段 #
按照两个字符串的结尾位置进行阶段划分。
2. 定义状态 #
定义状态 dp[i][j]
表示为:字符串 s
的前 i
个字符与字符串 p
的前 j
个字符是否匹配。
3. 状态转移方程 #
- 如果
s[i - 1] == p[j - 1]
,则字符串s
的第i
个字符与字符串p
的第j
个字符是匹配的。此时「字符串s
的前i
个字符与字符串p
的前j
个字符是否匹配」取决于「字符串s
的前i - 1
个字符与字符串p
的前j - 1
个字符是否匹配」。即dp[i][j] = dp[i - 1][j - 1]
。 - 如果
p[j - 1] == '.'
,则字符串s
的第i
个字符与字符串p
的第j
个字符是匹配的(同上)。此时dp[i][j] = dp[i - 1][j - 1]
。 - 如果
p[j - 1] == '*'
,则我们可以对字符p[j - 2]
进行0
~ 若干次数的匹配。- 如果
s[i - 1] != p[j - 2]
并且p[j - 2] != '.'
,则说明当前星号匹配不上,只能匹配0
次(即匹配空字符串),则「字符串s
的前i
个字符与字符串p
的前j
个字符是否匹配」取决于「字符串s
的前i
个字符与字符串p
的前j - 2
个字符是否匹配」,即dp[i][j] = dp[i][j - 2]
。 - 如果
s[i - 1] == p[j - 2]
或者p[j - 2] == '.'
,则说明当前星号前面的字符p[j - 2]
可以匹配s[i - 1]
。- 如果匹配
0
个,则「字符串s
的前i
个字符与字符串p
的前j
个字符是否匹配」取决于「字符串s
的前i
个字符与字符串p
的前j - 2
个字符是否匹配」。即dp[i][j] = dp[i][j - 2]
。 - 如果匹配
1
个,则「字符串s
的前i
个字符与字符串p
的前j
个字符是否匹配」取决于「字符串s
的前i
个字符与字符串p
的前j - 1
个字符是否匹配」。即dp[i][j] = dp[i][j - 1]
。 - 如果匹配多个,则「字符串
s
的前i
个字符与字符串p
的前j
个字符是否匹配」取决于「字符串s
的前i - 1
个字符与字符串p
的前j
个字符是否匹配」。即dp[i][j] = dp[i - 1][j]
。
- 如果匹配
- 如果
4. 初始条件 #
- 默认状态下,两个空字符串是匹配的,即
dp[0][0] = True
。 - 当字符串
s
为空,字符串p
右端有*
时,想要匹配,则如果「空字符串」与「去掉字符串p
右端的*
和*
之前的字符之后的字符串」匹配的话,则空字符串与字符串p
匹配。也就是说如果p[j - 1] == '*'
,则dp[0][j] = dp[0][j - 2]
。
5. 最终结果 #
根据我们之前定义的状态, dp[i][j]
表示为:字符串 s
的前 i
个字符与字符串 p
的前 j
个字符是否匹配。则最终结果为 dp[size_s][size_p]
,其实 size_s
是字符串 s
的长度,size_p
是字符串 p
的长度。
思路 1:动态规划代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(m n)$,其中 $m$ 是字符串
s
的长度,$n$ 是字符串p
的长度。使用了两重循环,外层循环遍历的时间复杂度是 $O(m)$,内层循环遍历的时间复杂度是 $O(n)$,所以总体的时间复杂度为 $O(m n)$。 - 空间复杂度:$O(m n)$,其中 $m$ 是字符串
s
的长度,$n$ 是字符串p
的长度。使用了二维数组保存状态,且第一维的空间复杂度为 $O(m)$,第二位的空间复杂度为 $O(n)$,所以总体的空间复杂度为 $O(m n)$。