题解 | 字符串通配符

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

int main() {
    string str1, str2;
    while (cin >> str1 >> str2) { //str1是pattern,str2是要匹配的
        int m = str1.size();
        int n = str2.size();

        vector<vector<bool>> v(m + 1, vector<bool>(n + 1,
                               false)); //这个含义是前i个
        //能否匹配字符串的前j个，能的话为true。
        v[0][0] = true;//pattern的前0个匹配字符串的前0个应该为true，大家都是空的
        
        for (int i = 1; i < m + 1; i++) {
            //'*'因为这个符号可以匹配0个
            if (str1[i - 1] == '*') //如果第i个字符为*
                v[i][0] = v[i -
                            1][0]; //为什么不直接赋值true,而要让他等于前一个值，因
            //为要防止这种情况'*A*'这个从2开始就该都是false的，如果直接赋值true或
            //者false那么第三个被错误赋值
            for (int j = 1; j < n + 1; j++) {
                if (str1[i - 1] == '*' &&
                        isalnum(str2[j - 1])) { //这里判断字符串里的必须
                    //要是字母或者数字，如果是符号的话，那么它的转移方程只有不用'*'的
                    //状态，也就是最后一个判断条件。举个例子pattern:t?t12*.* 字符串:
                    //txt123.xls  pattern'.'后面那个'*'和字符串的'.'应该是可以匹配的
                    //如果没有后面那个条件这里会直接跳过变为false
                    v[i][j] = v[i - 1][j] || v[i][j - 1]; //不用'*'和用'*'两种状态
                    //得到现在的状态
                } else if (toupper(str1[i - 1]) == (toupper(str2[j - 1]))) {
                    v[i][j] = v[i - 1][j - 1]; //这里先转换为大写还要判断相等，这个
                    //函数对其它符号不会改变
                } else if (str1[i - 1] == '?' && isalnum(str2[j - 1])) {
                    v[i][j] = v[i - 1][j - 1]; //如果是问好那么只能匹配一个，也就是
                    //根据前面来判断现在可不可以匹配
                } else if (str1[i - 1] == '*') { //这里就是第一个条件说的那个例外
                    v[i][j] = v[i - 1][j]; //只能是不用'*'的情况下的转移方程
                }
            }
        }
        cout << boolalpha << v[m][n] <<
             endl; //要输出pattern是否匹配字符串那么就是
        //前m个和字符串的前n个是不是true。

    }
}