题解 | 字符串通配符

#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;

bool isMatch = false;
void deepSearch(string& ss, string& sp, int cur_ss, int cur_sp) {
    if (isMatch)
        return ;
    if (cur_sp == sp.size() && cur_ss == ss.size()) {
        isMatch = true;
        return ;
    }
    if (cur_sp >= sp.size() || cur_ss >= ss.size()) 
        return ;
        
    char c1 = ss[cur_ss], c2 = sp[cur_sp];
    if (c1 != '*' && c1 != '?') {
        if (c1 == c2) {
            deepSearch(ss, sp, cur_ss + 1, cur_sp + 1);
        } else {
            return ;
        }
    }
    if (c1 == '*') {
        if(cur_ss == ss.size() - 1){
            isMatch = true;
            return ;
        }
        if (c2 >= 'a' && c2 <= 'z' || c2 >= '0' && c2 <= '9') {
            for (int i = cur_sp; i < sp.size(); ++i) {
                deepSearch(ss, sp, cur_ss + 1, i);
            }
        }
    }
    if (c1 == '?') {
        if (c2 >= 'a' && c2 <= 'z' || c2 >= '0' && c2 <= '9') {
            deepSearch(ss, sp, cur_ss + 1, cur_sp + 1);
        }
    }
    return ;
}

int main() {
    string s, sp, ss;
    cin >> s >> sp;
    for (auto& c : s) {
        if (c >= 'A' && c <= 'Z')
            c = c - 'A' + 'a';
        if(c == '*'){
            if(!ss.empty() && ss.back() == '*')
                continue;
        }
        ss.push_back(c);
    }
    for (auto& c : sp) {
        if (c >= 'A' && c <= 'Z')
            c = c - 'A' + 'a';
    }
    deepSearch(ss, sp, 0, 0);
    if (isMatch)
        cout << "true" << endl;
    else {
        cout << "false" << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")