题解 | #字符串通配符#

#include <cctype>
#include <iostream>
#include <cstring>
using namespace std;

int dfs(string pa,string s){
    int m=pa.size(),n=s.size();
    int f[m+1][n+1];
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=1;i<=m;i++){
        if(pa[i-1]=='*'){
            f[i][0]=f[i-1][0];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(pa[i-1]=='*' && isalnum(s[j-1])){
                if(f[i-1][j] || f[i][j-1] || f[i-1][j-1]){
                    f[i][j]=1;
                }
            }
            if(pa[i-1]=='?' && isalnum(s[j-1])){
                f[i][j]=f[i-1][j-1];
            }
            if(tolower(pa[i-1])==tolower(s[j-1])){
                f[i][j]=f[i-1][j-1];
            }
        }
    }
    return f[m][n];
}


int main(){
    string pa,s;
    std::cin >> pa >> s;
    if(1==dfs(pa,s)){
        std::cout << "true" << std::endl;
    }else{
        std::cout << "false" << std::endl;
    }
    return 0;
}