题目的主要信息：

• 实现如下2个通配符：

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

  ？：匹配1个字符

• 注：能被*和?匹配的字符仅由英文字母和数字0到9组成，输入却不止这两种

• 匹配不区分大小写

方法一：递归

具体做法：

可以在匹配部分过后，将通配符和字符串的剩余部分进入递归继续判断是否可以完成匹配。

首先优先级最高的是?，只能匹配一个数字或者单词，检查字符串中对应部分是否是数字或者单词，如果不是匹配失败，通过匹配成功，通配符和字符串同时向后移一位，将剩余部分作为子问题进入递归。

然后比较*，首先找到连续的所有*，因为不管有多少个，反正都是匹配0到多个字符，然后匹配0个、1个或者多个同时作为子问题送入递归，我们只要其中有一个能完成匹配，因此取或。

最后比较普通字符，全部转小写直接比较即可，能匹配，通配符和字符串同时向后移一位，将剩余部分作为子问题进入递归。

而递归的出口则是两个同时匹配到末尾说明匹配完成，如果其中一个到末尾另一个没到，说明不匹配。

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

bool ismatch(const char* reg, const char* str){
    if(*reg == '\0' && *str == '\0') //两个同时到末尾，匹配完成
        return true;
    if(*reg == '\0' || *str == '\0') //其中一个到末尾另一个没到，匹配失败
        return false;
    if(*reg == '?'){ //匹配单个数字或者字母
        if(!isdigit(*str) && !isalpha(*str)) 
            return false;
        return ismatch(reg + 1, str + 1); //同时后移进入子问题
    }else if(*reg == '*'){ 
        while(*reg != '\0' && *reg == '*') //连续的*也只能匹配0或多个数字或者字符
            reg++;
        reg--;
        return ismatch(reg + 1, str) || ismatch(reg + 1, str + 1) || ismatch(reg, str + 1); //0或者多个一起讨论
    }
    else if(tolower(*reg) == tolower(*str)) //其他字符自己匹配自己，不区分大小写
        return ismatch(reg + 1, str + 1);
    return false;
}
int main(){
    string reg, str;
    while(cin >> reg >> str){
        if(ismatch(reg.c_str(), str.c_str()))
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，其中$nn$为字符串和通配符字符串中较短一个的长度，树型递归
• 空间复杂度：$O(n)O(n)$，递归栈深度最多$nn$

方法二：动态规划

具体做法：

还可以用动态规划的方式，$dp[i][j]dp[i][j]$表示通配符前$ii$个字符与字符串前$jj$个字符是否匹配。首先$dp[0][0]dp[0][0]$都为空的时候，我么设定为匹配。然后首字母为*的时候可以匹配，其余转移如下：

• 遇到*号，可以选择匹配或者不匹配当前这个字符，于是有：$dp[i][j]=dp[i-1][j]\mathrm{\mid }\mathrm{\mid }dp[i][j-1]dp[i][j]\; =\; dp[i\; -\; 1][j]\; ||\; dp[i][j\; -\; 1]$

• 遇到普通符号，不区分大小写比较是否直接相等或者遇到？用来匹配数字或者字母，于是有：$dp[i][j]=dp[i-1][j-1]dp[i][j]\; =\; dp[i\; -\; 1][j\; -\; 1]$

最后检查$dp[m][n]dp[m][n]$即可直到是否完全匹配。

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

bool ismatch(string reg, string str){ //动态规划判断是否匹配
    int m = reg.length();
    int n = str.length();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); //dp[i][j]表示通配符前i个字符与字符串前j个字符是否匹配
    dp[0][0] = true; //都为空设置为匹配
    for(int i = 1; i <= m; i++){ //遍历通配符字符串
        dp[i][0] = dp[i - 1][0] && (reg[i - 1] == '*'); //首字符为*
        for(int j = 1; j <= n; j++){ //遍历字符串
            if(reg[i - 1] == '*') //遇到*
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; //选择匹配或者不匹配
            else{
                if(tolower(reg[i - 1]) == tolower(str[j - 1])) //不区分大小写的字符直接匹配
                    dp[i][j] = dp[i - 1][j - 1]; 
                if(reg[i - 1] == '?' && (isalpha(str[j - 1]) || isdigit(str[j - 1]))) //？匹配数字或者字母
                    dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}
int main(){
    string reg, str;
    while(cin >> reg >> str){
        if(ismatch(reg, str))
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$与$nn$分别是两个字符串的长度，遍历两层循环
• 空间复杂度：$O(mn)O(mn)$，dp数组的大小为$m\ast nm*n$