题解 | 正则表达式匹配

#include <iostream>
#include <vector>
using namespace std;

bool isMatch(string s,string p){
    int m=s.size(),n=p.size();
    //f[i][j]表示s的前i个字符能否与p的前j个字符匹配
    vector<vector<bool>>f(m+1,vector<bool>(n+1,false));
    //初始化
    f[0][0]=true;
    //如果p的当前一位为'*'，那么检查继承前两个位置的匹配状态（即允许 x* 匹配空字符串）
    for(int i=2;i<=n;i++){
        if(p[i-1]=='*'&&f[0][i-2])f[0][i]=true;
    }
    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
		    //如果p当前的字符不为'*'，那么很简单，只需检查s和p的当前字符能否匹配即可
            if(p[j-1]!='*'){
                if(p[j-1]=='.'||p[j-1]==s[i-1]){
                    f[i][j]=f[i-1][j-1];
                }
            }
		    //p当前字符为'*'，就比较复杂
            else {
                f[i][j]=f[i][j-2];//首先考虑x*匹配了0个字符
			    //接下来是匹配了多个字符的情况
                if(p[j-2]=='.'||p[j-2]==s[i-1]){
				    //能够从f[i-1][j]状态转移是因为 可以看做 s不考虑当前字符，而p中的x*匹配0次
                    f[i][j]=f[i][j]||f[i-1][j];
                }
            }
        }
    }
    return f[m][n];
}

int main() {
    string str,pattern;
    cin>>str>>pattern;
    cout<<(isMatch(str, pattern)?"true":"false")<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")