题目的主要信息：

在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求实现字符串通配符的算法，本题的通配符有：

*：匹配0个或以上的字符
？：匹配1个字符

注：能被*和?匹配的字符仅由英文字母和数字0到9组成。

方法一：

动态规划。dp[i][j]表示pattern前i个字符和字符串str前j个字符的的匹配情况，如果匹配，dp[i][j]=1；如果不匹配，dp[i][j]=0。初始化动态数组dp[0][0]=0，遍历一遍动态数组，假设pattern第i个字符为ch1，str数组第j个字符为ch2，：

如果ch1为 $*$ ，可以匹配或者不匹配。如果用*去匹配字符的话，dp[i][j]=dp[i][j-1]；如果忽略 $*$ ，则dp[i][j]=dp[i-1][j]。
如果ch1不为 $*$ ，考虑ch2的情况，如果ch2为数字，那么ch1必须为 $?$ 或者和ch2相同的数字才能匹配成功；如果ch2为字母，那么ch1必须为 $?$ 或者和ch2的大小写字母才能匹配成功；如果ch2既不为数字也不为字母，那么ch1必须和ch2相同才能匹配成功。

用以上方法更新dp数组，最后dp[pattern.size()][str.size()]表示两个字符串的匹配结果。 alt 具体做法：

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

using namespace std;

int match_string(string str,string pattern){
    int len1 = str.size();
    int len2 = pattern.size();
    vector<vector<int> > dp(len2+1,vector<int>(len1+1,0));
    //多加一行一列作为初始初值所用
    dp[0][0] = 1;//初始化
    for(int i=1;i <=len2;i++){
        char ch1 = pattern[i-1];
        ////设置每次循环的初值，即当星号不出现在首位时，匹配字符串的初值都为false
        dp[i][0] = dp[i-1][0]&&(ch1=='*');
        for(int j=1;j<=len1;j++){
            char ch2 = str[j-1];
        	if(ch1=='*'){
                dp[i][j]=dp[i-1][j]||dp[i][j-1]; //当匹配字符为*号时，可以匹配0个或者多个
            }else{
                if(isalpha(ch2)){//ch2为字母时，尝试是否能匹配
                    dp[i][j]=dp[i-1][j-1]&&(ch1=='?'||(ch2==ch1||ch2==(ch1+('A'-'a'))||ch2==(ch1-('A'-'a'))));
                }else if(isdigit(ch2)){//ch2为数字时，尝试是否能匹配
                    dp[i][j]=dp[i-1][j-1]&&(ch1=='?'||(ch1==ch2));
                }else {//ch2既不为字母也不为数字时，只有ch1和ch2相同才能匹配
                    dp[i][j]=dp[i-1][j-1]&&(ch1==ch2);
                }
            }

    	}
    }
    return dp[len2][len1];
}

int main(){
    string str1,str2;
    while(cin >> str1 >> str2){
       int flag =  match_string(str2,str1);
       if(flag){
           cout << "true" << endl;
       }else{
           cout << "false" << endl;
       }
    }
    
}

复杂度分析：

时间复杂度： $O (m n)$ ，需要遍历一遍dp数组。
空间复杂度： $O (m n)$ ，dp数组大小为mn。

方法二：

采用递归。首先判断第一个通配符：

如果为 $?$ ，只能匹配数字或字母，匹配一个字符，从下一个位置开始继续递归匹配。
如果为 $*$ ，首先要明白多个 $*$ 的效果和一个的效果是一样的，为了减少计算复杂度，将多个变为一个。 $*$ 号有三种情况，配0个（str+1,str1不用动），匹配1个（str和str1都往前移动1位），匹配多个（str不用动，str+1），分三种情况递归。
如果为其他字符，则要求与被匹配字符串的字符相同或者是它的大小写才能继续往下一个位置递归匹配。

两个字符串同时结束,递归结束，说明匹配成功；两个字符串中有一个先结束，递归结束，匹配失败。

具体做法：

#include<bits/stdc++.h>
using namespace std;

bool match(const char* s,const char* p){

    //两个字符串同时结束,返回true
    if((*p=='\0')&&(*s=='\0')){
        return true;
    }
     //两个字符串中有一个先结束，返回false
    if((*p=='\0')||(*s=='\0')){
        return false;
    }
    if(*p=='?'){//通配符为？时
        if(!isdigit(*s)&&!isalpha(*s)){//只能匹配数字或字母
            return false;
        }
        //匹配一个字符，从下一个位置开始继续匹配
        return match(s+1,p+1);
    }else if(*p=='*'){//通配符为！时
        while(*p=='*'){//多个*和一个*效果相同
            p++;
        }
        p--;
        //遇到*号，匹配0个（str+1,str1不用动），匹配1个（str和str1都往前移动1位），匹配多个（str不用动，str+1）
        return match(s,p+1) || match(s+1,p+1) ||  match(s+1,p);
    }else if(tolower(*p)==tolower(*s)){//不区分大小写
         //当前两字符相等，则进行下一个字符的匹配
        return match(s+1,p+1);
    }
    return false;//不满足上述三种情况，不匹配

}



int main(){
    string p,s;
    while(cin>>p>>s){
        bool res = match(s.c_str(),p.c_str());
        if(res){
            cout<<"true"<<endl;
        }else{
            cout<<"false"<<endl;
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (2^{n})$ ，最坏情况下，递归呈树形。
空间复杂度： $O (n)$ ，递归栈大小为n。

题解 | #字符串通配符#

题目的主要信息：

方法一：

方法二：