题解 | 字符串通配符

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

int main() {
    string s,p;
    cin>>s>>p;
    transform(s.begin(),s.end(),s.begin(),::tolower);
    transform(p.begin(),p.end(),p.begin(),::tolower);
    vector<vector<bool>> dp(s.size()+1,vector<bool>(p.size()+1,false));
    dp[0][0]=true;
    for(int i=1;i<=s.size();i++){
        if(s[i-1]=='*'&&dp[i-1][0])dp[i][0]=true;
    }
    for(int i=1;i<=s.size();i++){
        for(int j=1;j<=p.size();j++){
            if(s[i-1]=='*'){
                dp[i][j]=dp[i-1][j]||dp[i][j-1];
            }else if(s[i-1]=='?'){
                dp[i][j]=dp[i-1][j-1]&&isalnum(p[j-1]);
            }else{
                dp[i][j]=(s[i-1]==p[j-1])&&dp[i-1][j-1];
            }
        }
    }
    if(dp[s.size()][p.size()])cout<<"true";
    else cout<<"false";
}