题解 | #字符串通配符# leetcode44

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

bool re(string& pattern, string& text) {
    int m = pattern.size();
    int n = text.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    dp[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
        if (pattern[i - 1] == '*') {
            dp[i][0] = 1;
        } else {
            break;
        }
    }
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (pattern[i - 1] == '?') {
                if (isalnum(text[j - 1])) dp[i][j] = dp[i -1][j - 1];
            } else if (pattern[i - 1] == '*') {
                // 当不用'*'时dp[i][j] = dp[i - 1][j]
                // 当使用'*'，考虑'*'不能匹配符号，所以 dp[i][j] = isalnum(text[j - 1]) ?  dp[i][j - 1] : false;
                // 两者组合
                dp[i][j] = dp[i - 1][j] | (isalnum(text[j - 1]) ? dp[i][j - 1] : false);
            } else {
                if (tolower(pattern[i - 1]) == tolower(text[j - 1])) dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}
int main(){
    string pattern, text;
    cin >> pattern >> text;
    cout << boolalpha << re(pattern, text) << endl;
}