题解 | 字符串通配符

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

bool isMatch(const string& s, const string& p) {
    int m = s.length();
    int n = p.length();
    //dp[i][j] 表示s的前i个字符是否匹配p的前j个字符
    vector<vector<bool> > dp(m+1, vector<bool>(n+1, false));

    //初始化
    dp[0][0] = true;
    //检测s里面有没有* 因为*也能匹配空字符串
    for(int i = 0; i < m; ++i) {
        if(s[i] == '*') {
            dp[i+1][0] = dp[i][0];
        }
    }

    //填充dp数组
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(s[i-1] == '*') {
                if(isalnum(p[j-1])) { //是数字和字母的话 *可以为空也可以匹配p[j-1]
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                } else { //不是数字或者字母的话 *就只能为空了
                    dp[i][j] = dp[i-1][j];
                }
            } else if(s[i-1] == '?') {
                if(isalnum(p[j-1])) {
                    dp[i][j] = dp[i-1][j-1];
                } else dp[i][j] = false;
            } else {
                //如果是数字或其他特殊字符会返回其本身 只有是大写字母时才会发生改变返回小写字符
                if(tolower(s[i-1]) == tolower(p[j-1])) { 
                    dp[i][j] = dp[i-1][j-1];
                } else dp[i][j] = false;
            }
        }
    }
    return dp[m][n];
}


int main() {
    string s, p;
    cin >> s >> p;
    cout << (isMatch(s, p) ? "true" : "false") << endl;
    return 0;
}