题解 | #字符串通配符#

C++ 动态规划

题目增加了一些算例，导致现有的部分题解不能完全AC
原因是没有进行字符合法性的判断——“*：匹配0个或以上的字符（字符由英文字母，数字0-9和 '.' 组成，下同）”

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

/*判断字符是否符合通配要求*/
bool judge(char c)
{
    return (isalpha(c)||isalnum(c)||c=='.');
}
/*动态规划*/
bool match(string str1,string str2)
{
    int M = str1.size();
    int N = str2.size();
    vector<vector<bool>> dp(M+1,vector<bool>(N+1,false));
    dp[0][0] = true;
    for(int i=1;i<=M;++i){
        dp[i][0] = dp[i-1][0]&&(str1[i-1]=='*');//首字符为'*'的情况
        for(int j=1;j<=N;++j){
            if(str1[i-1]=='*'){
                dp[i][j] = dp[i-1][j]||dp[i][j-1];
            }else{
                if(tolower(str1[i-1])==tolower(str2[j-1]))//要么两字符相等
                    dp[i][j] = dp[i-1][j-1];
                if(str1[i-1]=='?' && judge(str2[j-1]))//要么？通配
                    dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    return dp[M][N];
}
int main(void)
{
    string str1,str2;
    while(cin>>str1>>str2){
        if(match(str1, str2)){
            cout << "true" << endl;
        }else{
            cout << "false" << endl;
        }
    }
    return 0;
}