题解 | 字符串通配符

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

int main() {
    string s,p;
    cin>>s>>p;
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;

    // 处理前导 *
    for (int i = 1; i <= m; ++i) {
        if (s[i - 1] == '*')
            dp[i][0] = dp[i - 1][0];
        else
            break;
    }

    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个字符（dp[i-1][j]），或者匹配一个字符（dp[i][j-1]）
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else if (sc == '?' && isalnum(pc)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (tolower(sc) == tolower(pc)) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }

    cout<<boolalpha<<dp[m][n];
}
// 64 位输出请用 printf("%lld")