题解 | #字符串通配符#

#include <iostream>
#include <cctype>
#include <unordered_map>
#include <string>
using namespace std;

unordered_map<string, bool> m;
string s1,s2;

bool dp(int i,int j){
    if(i==s1.length()) return j==s2.length();
    if(j==s2.length()) {
        while(s1[i]=='*'){
            i++;
        }
        if(i==s1.length()) return true;
        return false;
    }
    string key=to_string(i)+','+to_string(j);
    bool f;
    if(m.count(key)==1) return m[key];
    if(toupper(s1[i])==toupper(s2[j])) f=dp(i+1,j+1);
        else if(s1[i]=='?') {
            if (isdigit(s2[j]) || isalpha(s2[j])) {
                f=dp(i+1,j+1);
            } else {
                f = false;
            }
        }
            else if(s1[i]=='*') f=dp(i,j+1)||dp(i+1,j);
                else f=false;
    m[key]=f;
    return f;
}


int main() {
    cin>>s1>>s2;
    if(dp(0,0)) cout<<"true";
        else cout<<"false";
    return 0;
}
// 64 位输出请用 printf("%lld")

niu