字符串通配符——动态规划

 博客[1]中阐释了具体原理。

#include <iostream>
#include <string>
using namespace std;
class Solution{
public:
    static inline char toLowCase(const char c){
        if(c>='A'&&c<='Z'){
            return c+32;
        }else{
            return c;
        }
    }
    static inline bool IsValid(const char c){
        return isdigit(c)||(c>='a'&&c<='z')
               ||(c>='A'&&c<='Z');
    }
    static bool isMatch(const std::string &wildcard,
                   const std::string &input){
    int m=wildcard.size(),n=input.size();
    bool dp[m+1][n+1];
    dp[0][0]=true;
    for(int i=1;i<=m;i++){
        dp[i][0]=false;
    }
    for(int j=1;j<=n;j++){
        dp[0][j]=false;
    }
    for(int i=1;i<=m;i++){
        if('*'==wildcard.at(i-1)){
            dp[i][0]=true;
        }else{
            break;
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=false;
            if(toLowCase(wildcard.at(i-1))==
               toLowCase(input.at(j-1))){
                dp[i][j]=dp[i-1][j-1];
               }
            if('?'==wildcard.at(i-1)&&IsValid(input.at(j-1))){
                dp[i][j]=dp[i-1][j-1];
            }
            if('*'==wildcard.at(i-1)&&IsValid(input.at(j-1))){
                dp[i][j]=dp[i-1][j-1]||dp[i][j-1]||dp[i-1][j];
            }
        }
    }
    return dp[m][n];
}
};
int main(int argc,const char *argv[]){
    const char *res[]={
        "false",
        "true",
    };
    std::string wildcard="te?t*.*";
    std::string input="txt12.xls";
    getline(std::cin,wildcard);
    getline(std::cin,input);
    bool ret=Solution::isMatch(wildcard,input);
    std::cout<<res[ret]<<std::endl;
    return 0;
}

Reference：
[1] HJ71 字符串通配符