10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：
1 <= s.length <= 201 <= p.length <= 20s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
题解
久别重逢的leetcode题。
一开始的思路是用dfs暴力过，结果要么超时，要么爆内存。最后还是用dp过了。
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
static const int N = 30;
int dp[N][N];
bool isMatch(string s, string p) {
int lens = s.length(),lenp = p.length();
char t[N][2] = {};
int cnt = 0;
for (int i = 0;i < lenp; i++){
if (p[i + 1] == '*'){
t[cnt][0] = p[i];
t[cnt][1] = p[i + 1];
cnt++;
i++;
}else{
t[cnt++][0] = p[i];
}
}
bool start = false;
for (int i = 0; i < cnt; i++){
for (int j = 0; j < lens; j++){
if ((s[j] == t[i][0]) || (t[i][0] == '.')){
if (i == 0){
if (j == 0){
dp[i][j] = 1;
}
} else{
if (j == 0){
if (start == false){
dp[i][j] = 1;
}
} else{
dp[i][j] |= dp[i - 1][j - 1];
}
}
}
}
if (t[i][1] == '*'){
for (int j = 0; j < lens; j++){
if (i != 0){
dp[i][j] |= dp[i - 1][j];
}
if ((j != 0) && ((s[j] == t[i][0]) || (t[i][0] == '.'))){
dp[i][j] |= dp[i][j - 1];
}
}
} else{
start = true;
}
}
return dp[cnt-1][lens-1];
}
};
int main(){
string s,p;
cin>>s>>p;
cout<<Solution().isMatch(s,p);
}
以 s=abcd,p=a*b*c*.为例梳理一下思路。
对于p=a*b*c*.，将其拆分成a*，b*，c*，. 四个匹配操作。这样{}* 表示匹配0到多个{}内的字符，{} 表示匹配1个{}内的字符。对于每个匹配操作，不论它后面是否带*，都是要尝试能不能匹配1个{}字符的。我们用数组 char t[4][2] 来记录每一个匹配操作。
dp的行，枚举字符串p中匹配操作的个数。
dp的列，枚举字符串s中的每一个字符。
dp[i][j] 表示第i个匹配之后，子字符串s.substr(0,j+1)是否匹配成功。
先处理只匹配1个字符的情况。
当(s[j] == t[i][0]) || (t[i][0] == '.')成立，即匹配成功时
-
可以转移状态
dp[i][j] |= dp[i-1][j-1]。对应代码39行 -
需要注意当
j=0时，我们在匹配 s 中的第一个字符。如果 p 在匹配操作 i 之前，有一个必须匹配一个字符的操作，比如s=bb,p=ab*，这样子虽然t[1][0]==s[0]，匹配成功，但是 p 在这之前有个 a 是必须匹配的，所以不能进行状态转移。需要进行特判。这里用start来判断之前是否有必须要匹配的字符，即在匹配操作 i 之前，是否有存在一个操作没有*。
如果start==false，则直接将
dp[i][j] = 1即可。该部分对应代码34-38行。
-
当 i == 0，即在处理第0个匹配操作时，由于没有之前的状态可以进行转移，所以直接判断第一个字符是否匹配成功即可。对应代码29-33行
当 t[i][1]==*，即当前操作带*时
- 处理匹配0个的情况。该情况下，直接将上一行的 dp状态 转移到下一行即可，
dp[i][j] |= dp[i-1][j]。对应代码46-48行 - 处理匹配大于1个的情况。当前行已经处理好了匹配1个情况，因此在当前结果的基础上，如果
(j != 0) && ((s[j] == t[i][0]) || (t[i][0] == '.'))成立，则进行状态转移dp[i][j] |= dp[i][j - 1];。对应挨代码49-51行
最终输出 dp[cnt-1][lens-1]的值即可。
这里dp每一行最多20个bool类型，而且进行的操作都是或操作，因此可以用int类型来进行状态压缩。