题解 | 字符串通配符

#include <iostream>
#include <string>
#include <vector>
#include <cctype>  // 提供isalnum、tolower等函数

using namespace std;

int main() {
    string s, p;
    getline(cin, s);  // 读取通配符字符串
    getline(cin, p);  // 读取目标字符串

    int m = s.size();
    int n = p.size();

    // 创建DP表，dp[i][j]表示s[0..i-1]是否匹配p[0..j-1]
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

    // 边界条件：空s匹配空p
    dp[0][0] = true;

    // 处理s非空但p为空的情况：只有s全为*才能匹配空p
    for (int i = 1; i <= m; ++i) {
        dp[i][0] = dp[i - 1][0] && (s[i - 1] == '*');
    }

    // 填充DP表
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            char sc = s[i - 1];  // 当前通配符字符
            char pc = p[j - 1];  // 当前目标字符

            if (sc == '*') {
                // *可以匹配0个字符（继承i-1,j的结果），或匹配多个字符（需pc是字母/数字且继承i,j-1的结果）
                dp[i][j] = dp[i - 1][j] || (isalnum(pc) && dp[i][j - 1]);
            } else if (sc == '?') {
                // ?必须匹配1个字母/数字，且前序字符需匹配
                dp[i][j] = isalnum(pc) && dp[i - 1][j - 1];
            } else if (isalpha(sc)) {
                // 字母不区分大小写匹配，且前序字符需匹配
                dp[i][j] = (tolower(sc) == tolower(pc)) && dp[i - 1][j - 1];
            } else {
                // 其他字符（非*、?、字母）只能匹配自身，且前序字符需匹配
                dp[i][j] = (sc == pc) && dp[i - 1][j - 1];
            }
        }
    }

    cout << (dp[m][n] ? "true" : "false") << endl;

    return 0;
}