正则表达式匹配
题面
leetcode题目
给你一个字符串 \(s\) 和一个字符规律 \(p\)，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
- '.' 匹配任意单个字符
- '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖整个字符串\(s\)的，而不是部分字符串。
example-1
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
example-2
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
数据范围
- \(1 \leq s.length \leq 20\)
- \(1 \leq p.length \leq 30\)
- \(s\) 可能为空，且只包含从 \(a\)-\(z\) 的小写字母。
- \(p\) 可能为空，且只包含从 \(a\)-\(z\) 的小写字母，以及字符 \(.\) 和 \(*\)。
- 保证每次出现字符 \(*\) 时，前面都匹配到有效的字符
题解
总体思路
这题还是很麻烦的，思路不对的话写起来很痛苦，一开始dp的方向错了。
首先这样考虑，对于\(dp[i][j]\)我们认为他表示字符串\(s[i]\)与模式串$p[j]的匹配情况，那么最简单的情况有: \[dp[i][j] = dp[i-1][j-1] \land match(s[i], p[j])\] 其中: \[match(a,b) =
\begin{cases}
true &\text{$(a=b) \vee (b=.)$} \\
false &\text{otherwise}
\end{cases}\] 这表示我们当前字符恰好能完全匹配且前一段字符和前一段模式串也能完全匹配。接着，我们来考虑比较复杂的情况，即含有字符和'*'组合的模式串。
我们当然可以遍历该字符串可能出现的次数，并且一个一个的去计算出\(dp[i][j]\)的结果，这是可行的，但是会比较的繁琐，换个角度，我们这样看待问题，即: * 该字符与'*'的组合，在当前情况下被我们舍去，即字符出现了0次。(注意，这意味着后续我们都不考虑这个组合了) * 该字符与'*'的组合，在当前情况下匹配了我们的末尾字符s[i]，且后续要继续考虑是否能匹配.即我们匹配了s[i]之后就当s[i]不存在了。(这种情况等价于该组合至少出现了一次) 于是有: \[ dp[i][j] = dp[i][j-2] \vee (match(s[i],p[j-1]) \land (dp[i-1][j])
\] 上式子中的\(dp[i-1][j]\)表示重复的模式串出现了大于1次，至少说不含\(s[i]\)他是能匹配的。 \(dp[i][j-2]\)第一次出现表示当前重复字符出现了0次，即直接就舍弃掉了。
实际上这就能回答官方题解中的问题了:
在上面的状态转移方程中，如果字符串 \(pp\) 中包含一个「字符 + 星号」的组合（例如 \(a*\)），么在进行状态转移时，会先将 \(a\) 进行匹配（当 \(p[j]p[j]\) 为 \(a\) 时），再将 \(a*\) 作为整体进行匹配（当 \(p[j]p[j]\) 为 \(*\) 时）。然而，在题目描述中，我们必须将 \(a*\) 看成一个整体，因此将 \(a\) 进行匹配是不符合题目要求的。看来我们进行了额外的状态转移，这样会对最终的答案产生影响吗？这个问题留给读者进行思考。
从我的答案中也能看出，实际上我们没有重复的考虑，我们分别枚举了模式串中重复部分出现0次、1次和大于1次的情况。
!!! note 注意 初始化状态数组\(dp[i][j]\)时候，需要比较小心，空串对于类似只含有重复串的模式串也是能匹配上的
代码
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;
bool match(char a, char b)
{
return a == b || b == '.';
}
class Solution
{
public:
bool isMatch(string s, string p)
{
int lens = s.length();
int lenp = p.length();
int dp[lens + 1][lenp + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int j = 1; j <= lenp; j++)
{
if (p[j - 1] == '*' && dp[0][j - 2] == 1)
{
dp[0][j] = 1;
}
}
for (int i = 1; i <= lens; i++)
{
for (int j = 1; j <= lenp; j++)
{
if (match(s[i - 1], p[j - 1]) && dp[i - 1][j - 1] == 1)
{
dp[i][j] = 1;
}
if (p[j - 1] == '*' && j >= 2 && match(s[i - 1], p[j - 2]) && (dp[i - 1][j] == 1 ))
{
dp[i][j] = 1;
}
if (p[j - 1] == '*' && j >= 2 && dp[i][j - 2] == 1)
{
dp[i][j] = 1;
}
}
}
#ifdef _DEBUG
for (int i = 1; i <= lens; i++)
{
for (int j = 1; j <= lenp; j++)
{
cout << dp[i][j] << " ";
}
cout << endl;
}
#endif
return dp[lens][lenp];
}
};
int main()
{
Solution s;
string tests1 = "aa";
string testp1 = "a";
cout << s.isMatch(tests1, testp1) << endl;
string tests2 = "aa";
string testp2 = "a*";
cout << s.isMatch(tests2, testp2) << endl;
string tests3 = "ab";
string testp3 = ".*";
cout << s.isMatch(tests3, testp3) << endl;
string tests4 = "aab";
string testp4 = "c*a*b";
cout << s.isMatch(tests4, testp4) << endl;
string tests5 = "mississippi";
string testp5 = "mis*is*p*.";
cout << s.isMatch(tests5, testp5) << endl;
string tests6 = "aaa";
string testp6 = "ab*a";
cout << s.isMatch(tests6, testp6) << endl;
string tests7 = "aaa";
string testp7 = "ab*a*c*a";
cout << s.isMatch(tests7, testp7) << endl;
string tests8 = "aaca";
string testp8 = "an*a*c*a";
cout << s.isMatch(tests8, testp8) << endl;
return 0;
}
|