题解 | #字符串通配符#

37行完美解决，力扣44动态规划，只是这道题多了其他符号，那么其它符号就应该单独考虑

动态规划代码比较难以理解，下面详细解释。

#include <algorithm>
#include <vector>

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;i++){//这里字符串为空，初始化有pattern的时候判断有没有
        //'*'因为这个符号可以匹配0个
            if(str1[i-1]=='*')//如果第i个字符为*
            v[i][0] = v[i-1][0];//为什么不直接赋值true,而要让他等于前一个值，因
            //为要防止这种情况'*A*'这个从2开始就该都是false的，如果直接赋值true或
            //者false那么第三个被错误赋值
        }
        for(int i = 1;i<m+1;i++){
            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。
        
    }
}