Keshawn_lu's Blog

Leetcode 10. 正则表达式匹配

字数统计: 997阅读时长: 4 min
2020/06/20 Share

题目简介:

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.''*' 的正则表达式匹配。

1
2
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 .*

示例 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

思路:

又是一道看了解析也做的异常艰难的题…尽力把思路讲清楚吧

首先利用动态规划的思想,dp[i][j]代表s[0...i]p[0...j]是否能匹配成功。

为了方便处理边界问题,两个字符串都先在开头加上一个空格,初始化dp[0][0] = true

然后先初始化字符串s为空时,匹配的情况,也就是初始化dp[0][j]的值。只有当p[j] == '*'时,令p[j - 1]重复0次,也就是去掉p[j - 1], p[j]这两个字符,才有可能与空字符串匹配成功,此时dp[0][j] == dp[0][j - 2]

然后开始循环遍历sj字符串,会遇到以下这几种情况:

  1. p[j] != '*'时,若s[i] == p[j] || p[j] == '.',那么当前字符是匹配成功的,所以dp[i][j] == dp[i - 1][j - 1]
  2. p[j] == '*'时:
    1. 匹配0次,也就是将p[j - 1], p[j]都去除后能匹配成功,dp[i][j] == dp[i][j - 2]
    2. p[j - 1] == '.' || p[j - 1] == s[i]时,则dp[i][j]取决于dp[i - 1][j],因为在s最后加一个一样的字符也没有关系,即s[i] == s[i - 1],因为*可以匹配任意个相同的字符。所以dp[i][j] == dp[i - 1][j]。(aaaaaa*是匹配的,也就是*使末尾的a重复一次:a* == a)
    3. 综合上面两种情况,dp[i][j] == zero || one

最后返回dp[s.length() - 1][p.length() - 1]即可。

tip:

  • 开头加空格的方法很实用,利于代码的理解及后续操作。

代码如下:

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
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
bool isMatch(string s, string p) {

if(p.empty())
return s.empty();

vector<vector<bool>> dp(s.length() + 1, vector<bool>(p.length() + 1, false));

//处理边界,加空格
s = " " + s;
p = " " + p;

dp[0][0] = true;

//初始化
for(int j = 2; j < p.length(); j++){

if(p[j] == '*'){

dp[0][j] = dp[0][j - 2];
}
}

for(int i = 1; i < s.length(); i++){

for(int j = 1; j < p.length(); j++){

if(s[i] == p[j] || p[j] == '.') //当前匹配成功
dp[i][j] = dp[i - 1][j - 1];

if(p[j] == '*'){

bool zero; //匹配0次
bool one; //匹配1次

if(j - 2 >= 0){

zero = dp[i][j - 2];
}

//若dp[i - 1][j]已匹配成功,那么s[i] == s[i - 1],即在最后加一个一样的也没有关系,因为*可以匹配任意个相同的字符
one = dp[i - 1][j] && (p[j - 1] == '.' || p[j - 1] == s[i]);
dp[i][j] = zero || one;

}
}
}

return dp[s.length() - 1][p.length() - 1];

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: