题解 | #字符串通配符#

深度优先递归匹配字符
注意要将模式字符串中连续的替换为单个*，减少不必要的搜索。
注意字符匹配是大小不敏感的，并且只能匹配0-9, 字母以及.号。

#include <iostream>
#include <sstream>

using namespace std;

bool valid(char c) {
    if ((c >= '0' && c <= '9')
        || (c >= 'a' && c <= 'z')
        || (c >= 'A' && c <= 'Z')
        || c == '.') {
        return true;
    }
    return false;
}

char lower(char c) {
    if (c >= 'A' && c <= 'Z') {
        return c - 'A' + 'a';
    } else {
        return c;
    }
}

bool match(string &re_str, string &str, int p_re, int p) {

    while(p_re < re_str.size() && p < str.size()) {
        if ((re_str[p_re] == '?' && valid(str[p])
            || lower(re_str[p_re]) == lower(str[p])) ){
            p++;
            p_re++;
        } else if (re_str[p_re] == '*') {
            p_re++;
            while(p < str.size()) {
                if (match(re_str, str, p_re, p)) {
                    return true;
                }
                p++;
                if (p < str.size() && !valid(str[p])) {
                    return false;
                }
            }
        } else {
            break;
        }
    }
    if (p_re == re_str.size() && p == str.size()) {
        return true;
    } else {
        return false;
    }
}


string preprocess(string& re_str) {
    bool is_asterisk = false;

    stringstream ss;
    for(char c : re_str) {
        if (c == '*') {
            if (is_asterisk) {
                continue;
            }
            is_asterisk = true;
        } else {
            is_asterisk = false;
        }
        ss << c;
    }
    return ss.str();
}

int main() {
    string str;
    string re_str;

    while(getline(cin, re_str)) {
        getline(cin, str);
        re_str = preprocess(re_str);
        if (match(re_str, str, 0, 0)) {
            cout << "true" << endl;
        } else {
            cout << "false" << endl;
        }
    }

    return 0;
}