题解 | #字符串通配符#

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

// 判断两个字符是否相等（不区分大小写）
bool charEquals(char a, char b) {
    return tolower(a) == tolower(b);
}

// 判断字符是否为英文字母或数字
bool isValidChar(char c) {
    return isalnum(c);  // isalnum 用于判断字符是否为字母或数字
}

// 实现通配符匹配
bool isMatch(const string& pattern, const string& str) {
    int m = pattern.size();
    int n = str.size();

    // dp[i][j] 表示 pattern 的前 i 个字符与 str 的前 j 个字符是否匹配
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

    // 初始化 dp[0][0] 为 true，因为空模式和空字符串是匹配的
    dp[0][0] = true;

    // 处理 pattern 以 '*' 开始的情况，* 可以匹配空字符串
    for (int i = 1; i <= m; i++) {
        if (pattern[i - 1] == '*') {
            dp[i][0] = dp[i - 1][0];
        }
        else {
            break;
        }
    }

    // 填充 dp 表格
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (pattern[i - 1] == '*') {
                // '*' 可以匹配零个或多个字符
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
            else if (pattern[i - 1] == '?') {
                // '?' 必须匹配一个英文字母或数字
                dp[i][j] = dp[i - 1][j - 1] && isValidChar(str[j - 1]);
            }
            else {
                // 普通字符匹配，区分大小写
                dp[i][j] = dp[i - 1][j - 1] && charEquals(pattern[i - 1], str[j - 1]);
            }
        }
    }

    // 返回最终结果
    return dp[m][n];
}

int main() {
    string pattern, str;
    while (cin >> pattern >> str) {
        if (isMatch(pattern, str)) {
            cout << "true" << endl;
        }
        else {
            cout << "false" << endl;
        }
    }
    return 0;
}