题解 | #字符串通配符#

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

int main() {
    string s1,s2;
    while(cin >> s1 >> s2){
        int m = s1.length();//通配符字符串长度
        int n = s2.length();//匹配字符串长度
        vector<vector<int> > dp(m+1,vector<int>(n+1,0));//dp[m][n]表示通配字符串前m位与匹配字符串前n位匹配情况，匹配为1
        dp[0][0] = 1;//都为空，匹配
        for(int i = 1 ; i <= m; i++) dp[i][0] = dp[i-1][0] & (s1[i-1] == '*');//只要通配符字符串全为 *  则dp[i][0] = 1 匹配
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s1[i-1] == s2[j-1] || tolower(s1[i-1]) == s2[j-1] || toupper(s1[i-1]) == s2[j-1])//两字符匹配,字母不区分大小写
                    dp[i][j] = dp[i-1][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] == '*' && (isdigit(s2[j-1]) || isalpha(s2[j-1])))//通配符为 * 且匹配字符为数字或字母
                    dp[i][j] = dp[i-1][j-1] || dp[i-1][j] || dp[i][j-1];//通配符*与字符x匹配分三种：1.下标一样时匹配，继承dp[i-1][j-1] 
                //2.错位匹配时 继承dp[i][j-1] 3.匹配0个字符时(即忽略不用) 继承dp[i-1][j]
            }
        }
        if(dp[m][n]) cout << "true" << endl;
        else cout << "false" << endl;
    }
}
// 64 位输出请用 printf("%lld")