题解 | #字符串通配符#

主要还是采用动态规划的方法，以滚动数组的方式来呈现，可以用dp[N][M]的方式来帮助理解，表示S[N]字符结尾和S1[M]结尾的字符串中存在连续相等字符串的长度为dp[N][M],重点是递推公式：

1. tolower(s[i]) == tolower(s1[j])，两者字符相等，则就dp[i-1][j-1]+1
2. (s[i] == '?' && !ispunct(s1[j])，以为这当s[i]为?，并且s1[j]是字母的数字的时候，?可以替换对应字符，也是dp[i-1][j-1]+1
3. s[i] == '*'，这种最难处理，因为它可以等价于0或n个，所以需要从有效的字符数开始，也就是默认前面的*都没有替换（即删除*），因为可以替换n个，也就是累加前一个长度dp[i][j - 1] + 1，也可以是当前替换当前字符dp[i-1][j-1]+1，两者取最大

#include <cctype>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
    string s, s1;
    while (cin >> s >> s1) { // 注意 while 处理多个 case
        vector<int> dp(s1.size(), 0);
        int index = 0;
        for (int i = 0; i < s.size(); i++) {
            int pre = 0;
            for (int j = 0; j < s1.size(); j++) {
                int temp = dp[j];
                if ((s[i] == '?' && !ispunct(s1[j])) || tolower(s[i]) == tolower(s1[j])) {
                    dp[j] = pre + 1;
                } else if (s[i] == '*') {
                        dp[j] = (j >= (i - index) ? max(dp[j - 1] + 1,pre +1) : dp[j]);
                } else {
                    dp[j] = 0;
                }
                pre = temp;
                // cout << dp[j] << " ";
            }
            index += (s[i] == '*' ? 1 : 0);
            // cout << endl;
        }
        // cout << dp[s1.size() - 1] << endl;
        cout << (dp[s1.size() - 1] == s1.size() ? "true" : "false") << endl;
    }
    return 0;
}