博客[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 字符串通配符
