题解 | #字符串通配符#

#include <bits/stdc++.h>

using namespace std;

string s1,s2;
int len1,len2;

//递归
bool f(int x,int y){
    if(x>=len1&&y>=len2){//成功匹配
        return true;
    }
    if(x>=len1||y>=len2)
        return false;
    if(s1[x]=='*'){
        int i=x;
        while(i<len1&&s1[i]==s1[i+1]){//多个连续的*,只取最后一个*匹配
            i++;
        }
        if(f(i+1,y))//匹配0个字符
            return true;
        for(int j=y;j<len2;j++){//匹配至少一个字符
            if(!isalpha(s2[j])&&!isdigit(s2[j])){//*只能匹配英文字母和数字0到9
                break;
            }
            if(f(i+1,j+1))
                return true;
        }
    }else if(s1[x]=='?'){
        if(!isalpha(s2[y])&&!isdigit(s2[y]))//?只能匹配英文字母和数字0到9
            return false;
        if(f(x+1,y+1))
            return true;
    }else{
        if(s1[x]==s2[y])//相等，则递归下去
            if(f(x+1,y+1))
                return true;
        else
            return false;
    }
    return false;
}
int main(){
    
    while(cin >> s1 >> s2){
        len1=s1.size(),len2=s2.size();
        for(int i=0;i<len1;i++){//转化成大写
            if(s1[i]>='a'&&s1[i]<='z'){
                s1[i]-=32;
            }
        }
        for(int i=0;i<len2;i++){//转化成大写
            if(s2[i]>='a'&&s2[i]<='z'){
                s2[i]-=32;
            }
        }
        if(f(0,0))//递归
            cout << "true\n";
        else
            cout << "false\n";
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

string s1,s2;
int len1,len2;
int dp[105][105];

int main(){
    
    while(cin >> s1 >> s2){
        len1=s1.size(),len2=s2.size();
        for(int i=0;i<len1;i++){//转化成大写
            if(s1[i]>='a'&&s1[i]<='z'){
                s1[i]-=32;
            }
        }
        for(int i=0;i<len2;i++){//转化成大写
            if(s2[i]>='a'&&s2[i]<='z'){
                s2[i]-=32;
            }
        }
        memset(dp,0,sizeof(dp));
        //动态规划
        dp[0][0]=1;//初始化
        for(int i=1;i<=len1;i++)
            dp[i][0]=dp[i-1][0]&&(s1[i-1]=='*');
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(s1[i-1]=='*'){//用*匹配
                    dp[i][j]=dp[i-1][j]||dp[i][j-1];
                }else if(s1[i-1]=='?'&&(isdigit(s2[j-1])||isalpha(s2[j-1]))){//用?匹配
                    dp[i][j]=dp[i-1][j-1];
                }else if(s1[i-1]==s2[j-1]){//其他情况
                    dp[i][j]=dp[i-1][j-1];
                }
            }
            
        }
        
        if(dp[len1][len2])//判断结果
            cout << "true\n";
        else
            cout << "false\n";
    }
    return 0;
}