题目
请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.’表示任意一个字符,而’*‘表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”ab*ac*a”匹配,但与”aa.a”和”ab*a”均不匹配。
示例 1:
1
2
3
4
5 输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。示例 2:
1
2
3
4
5 输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。示例 3:
1
2
3
4
5 输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。示例 4:
1
2
3
4
5 输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。示例 5:
1
2
3
4 输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
- s 可能为空,且只包含从 a-z 的小写字母。
- p 可能为空,且只包含从 a-z 的小写字母以及字符 . 和 *,无连续的 ‘*‘。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
正则表达式匹配,返回是否匹配,为了解决问题,我们至少需要将两个字符串各遍历一遍。由于匹配肯定是从前向后依次匹配,那么字符串的所有前缀一定都有与其相匹配的正则表达式前缀。
试想这个例子:
1 | s = "mississippi" |
对于m
,匹配,没有其他选择,下一个是i
,匹配,直到s
与*
匹配,遇到*
时,它可以代表它之前的字母,也可以代表空字符(忽略该符号)。对于第一个*
,我们发现其第一种情况是匹配的,因此需要进行下一次选择,此时可以选择结束*
的匹配,或者继续*
的匹配,本例中,选择继续匹配之后会匹配失败,需要重置选择,重新选择结束匹配,去匹配i
和i
,直到遇到i
与p
的匹配,此时不匹配,不匹配时有以下选择:检查正则表达式下个字符是否为*
,如果是,那么可以跳过当前字符和*
,用*
后的字符继续匹配,否则匹配失败。
以上流程可以用回溯实现,因为有些操作需要撤销重做。
需要特判的条件是,匹配空字符,只有前面有合法字符的*
才可以匹配空字符,两个空字符匹配代表匹配成功。
四小时后:
终于做出来了
1 | class Solution { |
为了避免时间浪费,一定要捋清楚条件判断的层次结构。
就这道题来说,动态规划的状态很好想,但是难点在于针对不同的情况我们要做不同的选择,而不是简单堆砌选择。
- 遇到
*
s
为空,跳过*
s
非空,匹配
- 遇到其他
s
非空,匹配s
空,返回匹配失败
写完就能看到那个下面代码了。需要注意的地方是,对于空了的s
,dp 数组中没有对应的位置,因为无意义,所以需要直接返回而不填数组。
每次递归时间复杂度$O(1)$,递归深度为$SP$,因此时间复杂度$O(SP)$,即两字符串长度之积。
因此,为了正则匹配,我们需要遍历两个字符串,一个不含正则表达式,一个含有正则表达式。
假设两个指针ps
,pp
分别初始化为指向s
和p
的首元素,s
为匹配字符串,p
为匹配模式,在匹配过程中:
- 字符匹配常规字符
- 若匹配,move on
- 不匹配,检查模式字符的后一个字符是否存在,若存在且为
*
,move on;否则,返回 false
- 字符匹配正则表达式字符
- 匹配到
.
,move on - 匹配到
*
,查询上一个元素(不能是*
,只能是常规字符或.
),并匹配,若匹配成功,move on,否则返回 false
- 匹配到
- 结束条件:两个字符串到达结尾;
s
到达结尾,p
未到达结尾,若p
当前字符为*
那么返回true,否则为false;p
到达结尾,s
未到达结尾,返回false
按照题目意思,连续两个 *
是非法输入。
此外特殊情况还应该包含空字符串输入。
还有一种特殊情况:例如
1 | "aaa" |
这种输入使得算法满足s
结束而p
未结束的条件,且不以*
结尾。概括一下这种特殊情况:*
前后元素相同。
条件越想越复杂,干脆看题解。
题解的思路是动态规划,其实具体说就是对于匹配到*
的情况,此时有两种选择:
- 忽略,不匹配
- 匹配一个字符
两种选择只要有一个成功匹配即可。下面讨论状态转移:
问题可以分解为子问题:子串是否可以匹配。记dp[i][j]
为s
的前i
个和p
的前j
个字符组成的字符串匹配,那么当
- 字符匹配常规字符
- 若匹配,检查
dp[i-1][j-1]
是否为true
- 不匹配,那么
dp[i][j]
只能为false
- 若匹配,检查
- 字符匹配正则表达式字符
- 匹配到
.
,检查dp[i-1][j-1]
- 匹配到
*
- 选择不匹配,直接检查
dp[i][j-2]
- 选择匹配,检查
- 选择不匹配,直接检查
- 匹配到
1 | class Solution { |
上面是暴力递归,暴力回溯,没有动态规划。