题解 | #字符串通配符#

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

bool chCop(char a, char b) {
    if (a == b) {
        return true;
    }
    char temp1, temp2;
    if (isalnum(a) && isalnum(b)) {

        if (islower(a)) {
            temp1 = toupper(a);
        } else {
            temp1 = a;
        }

        if (islower(b)) {
            temp2 = toupper(b);
        } else {
            temp2 = b;
        }

        if (temp1 == temp2) {
            return true;
        }
    }
    return false;
}

int main() {
    string str, pattern;
    getline(cin, pattern);
    getline(cin, str);

    vector<vector<bool>> dp(pattern.size() + 1, vector<bool>(str.size() + 1,
                            false));

    dp[0][0] = true;
    for (int i = 1; i <= pattern.size(); i++) {
        dp[i][0] = dp[i - 1][0] && (pattern[i - 1] == '*');
        for (int j = 1; j <= str.size(); j++) {
            if (pattern[i - 1] == '*' && isalnum(str[j - 1])) {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];
            } else if (pattern[i - 1] == '?' && isalnum(str[j - 1])) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = chCop(pattern[i - 1], str[j - 1]) && dp[i - 1][j - 1];
            }
        }
    }

    if (dp[pattern.size()][str.size()]) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
}

dp数组，dp[i][j]表示以pattern[i-1]为尾巴，str[j-1]为尾巴的字符串是否匹配

// 初始化

// dp[0][0] 为真,0匹配0可行

// dp[0][j] 为假,0无法匹配任何字符串

// if(pattern[i-1] 和 str[j-1]完全相同)

// 如果dp[i-1][j-1]为真，则dp[i][j]为真

// else if(pattern[i]== '*'且str[j-1]是字母或数字)

// dp[i-1][j](匹配0个字符)

// 或者 dp[i][j-1](匹配任意多字母)

// 或者dp[i-1][j-1] (匹配一个字符)

// 任意一个情况符合即可

// else if(pattern[i] == '?'且str[j-1]是字母或数字)

// dp[i][j] = dp[i-1][j-1]