题解 | 字符串通配符

#include <cctype>
#include<string>
#include<iostream>
#include<vector>

using namespace std;
int main() {
    string s, p;
    cin >> s >> p;
    vector <vector<int>>dp(s.size() + 1, vector<int>(p.size() + 1, 0));
    dp[0][0] = 1;
    char ch1;
    for (int i = 1; i <= s.size(); i++) {
        ch1 = s[i - 1];
        dp[i][0] = dp[i - 1][0] && ch1 == '*';
    }
    for (int i = 1; i <= s.size(); i++) {
        ch1 = s[i - 1];
        for (int j = 1; j <= p.size(); j++) {
            char ch2 = p[j-1];
            if (ch1 == '*') {
                if (isalnum(ch2)) {//只有在第二个字符是数字或者字母时才生效
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                    continue;
                } else {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
            }
            if (isalpha(ch2)) {
                if (ch1 == '?' || toupper(ch1) == toupper(ch2)) {
                    dp[i][j] = dp[i - 1][j - 1];
                    continue;
                }
            } else if (isdigit(ch2)) {
                if (ch1 == '?' || ch1 == ch2) {
                    dp[i][j] = dp[i - 1][j - 1];
                    continue;
                }
            }
            else if(ch1==ch2){
                    dp[i][j] = dp[i - 1][j - 1];
                    continue;
                }
        }
    }
    if(dp[s.size()][p.size()]==1)cout<<"true";
    else cout<<"false";
}

一开始完全没想到用动态规划去求解，后面参考了2021年一个牛友发的题解https://blog.nowcoder.net/n/ed2ff73aee41422c8bfc7089ead67567?f=comment，不过他的代码也不严谨。'*'只能匹配数字或字母，不能匹配其他字符。我修改了一下。