题解 | #正则表达式匹配#

解题思路：

• 题是写出来了，但是感觉像假做。可能是测试数据不行。有时写递归感觉心里没底。先递归解决问题，再记忆化，就成了dp，估计后面还有优化的空间。有时候写dp，先费劲脑力把递归思路想出来。管它什么套路。
• 首先考虑一般情况。想要使得str和pattern匹配，从结尾开始，考虑我从哪里来。这里要分一些情况：

1. 使用i，j来表示两个串的末尾坐标，假如$str[i]==pattern[j]orpattern[j]=={}^{\mathrm{\prime }}{\mathrm{.}}^{\mathrm{\prime }}str[i]\backslash \; ==\backslash \; pattern[j]\backslash \; or\backslash \; pattern[j]\backslash \; ==\backslash \; \text{'}.\text{'}$,$dp[i][j]=dp[i-1][j-1]dp[i][j]\; =\; dp[i-1][j-1]$.
2. 假如$pattern[j]=={}^{\mathrm{\prime }}{\ast }^{\mathrm{\prime }}pattern[j]\backslash \; ==\backslash \; \text{'}*\text{'}$,那么情况就稍微复杂：即，如果当前是‘*’号，要么由一次匹配而来，要么当前做0次匹配，直接再往前匹配。

• 接下来是边界条件：

1. 这里多了个特殊的边界条件，，因为在贪婪匹配的过程中，会导致i被用完而<0，那么如果，则需要去判断pattern剩余部分是否由$(\mathrm{"}a\ast \mathrm{"}-\mathrm{"}z\ast \mathrm{"})("a*"-"z*")$这样的组合组成，只要满足的就可以把这部分都进行0次匹配返回true。
2. 边界条件2，当时，只要判断$pattern[j]=={}^{\mathrm{\prime }}{\ast }^{\mathrm{\prime }}\mathrm{\mid }\mathrm{\mid }pattern[j]==str[i]pattern[j]\backslash \; ==\backslash \; \text{'}*\text{'}\backslash \; ||\backslash \; pattern[j]\backslash \; ==\backslash \; str[i]$即可。

#include<bits/stdc++.h>
using namespace std;
int solve(string &s1, string &s2, int i, int j, vector<vector<int>> &dp){
    
    if(i < 0 ){//贪婪匹配后，造成str被用完。
      //只需要剩下部分满足字母+*的组合就匹配成功
        int flag = 1;
        for(int l = 0; l <= j; l+=2){
            if (s2[l] != '*' && s2[l+1] == '*')continue;
            else flag = 0;
        }
        return flag;
    }
    if(dp[i][j] != -1) return dp[i][j];
    if(i == 0 && j == 0){//两边只剩一个点的匹配，'.'可以匹配任何字符，要么两边为同一个字符。
        if(s2[j] == '.' || s2[j] == s1[i]) dp[i][j] = 1;
        else dp[i][j] = 0;
    }
    else{//当前字符匹配成功后，结果只和前值有关
        if(s1[i] == s2[j] || s2[j] == '.') dp[i][j] = solve(s1, s2, i-1, j-1, dp);
      //如果遇见‘*’号则进行贪婪匹配或者0次匹配。
        else if(s2[j] == '*') dp[i][j] = ((s1[i] == s2[j-1] || s2[j-1] == '.') && solve(s1, s2, i-1, j, dp)) || solve(s1, s2, i, j-2, dp);
        else dp[i][j] = 0;
    }
    return dp[i][j];
}
int solve3(string &s1, string &s2){//递推
    vector<vector<int>> dp(s1.size(), vector<int>(s2.size()));
    dp[0][0] = (s1[0] == s2[0] || s2[0] == '.');
    if(s2[1] == '.' || s2[1] == s1[0]) dp[0][1] = 1 - dp[0][0];
    else if(s2[1] == '*') dp[0][1] = dp[0][0];
    for(int j = 2; j < s2.size(); ++j){//初始化i=0行
        if( s2[j] =='.' || s2[j] == s1[0]) {
            int flag = 0;
            for(int l = 1; l <= j; l+= 2){
                if (s2[l] != '*'){
                    flag = 1;
                    break;
                }
            }
            dp[0][j] = 1 - flag;
        }
        else if(s2[j] == '*'){
            dp[0][j] = dp[0][j-1] || dp[0][j-2];
        }
    }
    for(int i = 1; i < s1.size(); ++i){//一般情况，遇到*号时，分匹配还是不匹配做出选择。
        for(int j = 1; j < s2.size(); ++j){
            if (s2[j] == '.' || s2[j] == s1[i]) dp[i][j] = dp[i-1][j-1];
            else if(s2[j] =='*') dp[i][j] = (dp[i-1][j] && (s2[j-1] == s1[i] || s2[j-1] == '.')) || (j>=2? dp[i][j-2]:0);
        }
    }
    return dp[s1.size()-1][s2.size()-1];
}
int main(){
    string s1, s2;
    cin>>s1;
    cin>>s2;
    vector<vector<int>> dp(s1.size(), vector<int>(s2.size(),-1));
    solve(s1,s2,s1.size()-1,s2.size()-1,dp);
    int flag = solve(s1,s2,s1.size()-1, s2.size()-1, dp);
    flag? cout<<"true"<<endl : cout<<"false"<<endl;
    return 0;
}