面试题.正则表达式匹配
请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:
输入:
s = “ab”
p = “.”
输出: true
解释: “.” 表示可匹配零个或多个（’*’）任意字符（’.’）。
示例 4:
输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:
输入:
s = “mississippi”
p = “misisp*.”
输出: false
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ‘’。
注意：本题与主站 10 题相同：https://leetcode-cn.com/problems/regular-expression-matching/
解题思路
解题代码
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
|
class Solution {
public:
bool isMatch(string s, string p) {
int n= s.size(),m = p.size();
// if(n==0) return m==0;
if(m==0) return n==0;
//dp[i,j] = a[i]==b[i] && dp[i-1,j-1] || (dp[i-1,j]||dp[i,j-1])
vector<vector<bool>> dp(n+1,vector<bool>(m+1));
//构造p 的表达式
dp[0][0] = true;
for(int i=1;i<=m;i++) {
if(p[i-1]=='*') dp[0][i] = dp[0][i-2];//****,表示任意字符
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
char x = s[i-1];
char y = p[j-1];
if(x==y || y=='.' ) {
//匹配到 1
dp[i][j] = dp[i][j]|dp[i-1][j-1];
}
else if(y=='*' && j>=2 ) {
//匹配0 个字符
//* 依赖于前面的字符
char prey = p[j-2];
dp[i][j] =dp[i][j] | dp[i][j-2];//匹配0个字符，当前* 无用
//匹配前一个字符
// char prey = p[j-2];
if ( prey == x || prey == '.')
//匹配前1个字符，prex is s[i-1]
dp[i][j] = dp[i][j]| dp[i-1][j];
}
}
}
return dp[n][m];
}
};
|
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
|
class Solution {
public:
bool isMatch(string s, string p) {
int n= s.size(),m = p.size();
// if(n==0) return m==0;
if(m==0) return n==0;
//dp[i,j] = a[i]==b[i] && dp[i-1,j-1] || (dp[i-1,j]||dp[i,j-1])
vector<vector<bool>> dp(n+1,vector<bool>(m+1));
//构造p 的表达式
dp[0][0] = true;
for(int i=1;i<=m;i++) {
if(p[i-1]=='*') dp[0][i] = dp[0][i-2];//****,表示任意字符
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
char x = s[i-1],y = p[j-1];
if( y == '*' && j>=2) {
//匹配0 个a ,例如 a*
dp[i][j] = dp[i][j-2];
if( s[i-1] == p[j-1-1] || p[j-1-1] == '.') {
//匹配 1-n 个 a
dp[i][j] = dp[i][j] | dp[i-1][j];
}
}else if (x== y || y == '.') {
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[n][m];
}
};
|
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
|
#define p pattern
class Solution {
public:
bool match(string str, string pattern) {
int n = str.size(),m = pattern.size();
vector<vector<int>> dp(n+1,vector<int> (m+1));
// . *[前面的字符出现0-n]
dp[0][0] = 1;
for(int i=1;i<=m;i++) dp[0][i] = dp[0][i-2] && pattern[i-1]=='*';
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
char x,y;
x = str[i-1],y = pattern[j-1];
if (x== y || y == '.' ) {
dp[i][j] = dp[i-1][j-1];
} else if(y=='*' && y>=2) {
char prey = pattern[j-1-1];
if(prey == '.' || prey == x) {
dp[i][j] = dp[i][j-2];//匹配 0个，不匹配【*】没有用到
dp[i][j] |= dp[i-1][j];//匹配 n次, * 匹配 pre 或者 .
}else {
dp[i][j] = dp[i][j-2];//匹配0个字符，不匹配
}
}
}
}
return dp[n][m];
}
};
|
