题解 | #字符串通配符#

#include <algorithm>
#include <cctype>
#include <string>
#include <vector>
 #include <iostream>
using namespace std;
/*用动态规划可以参考动态规划做判断是否回文子串那道题，HJ32 这道也是由bool类型的dp数组来表示是否能匹配上。
1）dp[i][j] 表示[0，i-1]的pattern串是否能和[0,j-1]的s串匹配成功
2）递推：
   1>如果p[i-1]是*，s[j-1]是英语或数字，可以匹配，所以就可以选择用或者不用，不用的话，就考虑[i-2]的p串和[j-1]的s串是否匹配，用的话，就考虑[i-1]的p串和[j-2]的s串是否匹配 （ps.因为用*的话，s串最后一位一定是匹配的，可以去掉最后一位看前面是否还能和p匹配，当然前面也可以用*所以判断的p串还是原长度）
即 dp[i][i]=dp[i-1][j]||dp[i][j-1];
   2>如果p[i-1]是*，s[j-1]不是英语或数字，无法匹配，就等于*匹配了0个字符，只能看p串[i-2]和s串[j-1]是否匹配了，即dp[i][j]=dp[i-1][j];
   3>如果p[i-1]和s[j-1]相等，注意这里可能是数字或者英文，英文不区分大小写，那就只看p串[i-2]和s串[j-2]是否能匹配，即dp[i][j]=dp[i-1][j-1];
   4>如果p[i-1]是？且s[j-1]是英文和字母，？匹配一位，则dp[i][j]=dp[i-1][j-1]
   其他情况，p[i-1]和s[j-1]直接不相等，或者？对应了非字母，那就一定是false，可以全部初始化为false，就不用特意考虑false的递推
3）初始化  递推方向从(i-1,j)->(i,j)  (i,j-1)->(i,j)  (i-1,j-1)->(i,j)所以需要初始化第一行第一列。dp[0][0]=true,相当于空串对空串
后面的dp[0][j]=false 空串都匹配不上；后面的dp[i][0]要考虑i-1的P串有没有有没有* if(p[i-1]==*) dp[i][0]=dp[i-1][0];
4) 遍历顺序，i,j都要是从小到大*/
int main() { 
    string pattern, s;
    while(cin>>pattern>>s){
        int plen=pattern.size();
        int slen=s.size();
        vector<vector<bool>>dp(plen+1,vector<bool>(slen+1,false));
        //初始化
        dp[0][0]=true;
        for(int i=1;i<=plen;i++){
            if(pattern[i-1]=='*'){dp[i][0]=dp[i-1][0];}
            //cout<<"dp"<<i<<"0="<<dp[i][0]<<" ";
        }
        //遍历
        for(int i=1;i<=plen;i++){
            for(int j=1;j<=slen;j++){
                if(pattern[i-1]=='*'&&(isalpha(s[j-1])||isdigit(s[j-1]))){
                    dp[i][j]=dp[i-1][j]||dp[i][j-1];
                }
                else if(pattern[i-1]=='*'){//s[j-1]不是英文和数字了，*只能匹配0个
                    dp[i][j]=dp[i-1][j];
                }
                else if(toupper(pattern[i-1])==toupper(s[j-1])){
                    //toupper用在数字上会返回原数字
                    dp[i][j]=dp[i-1][j-1];
                }
                else if(pattern[i-1]=='?'&&(isalpha(s[ j-1])||isdigit(s[j-1]))){
                    dp[i][j]=dp[i-1][j-1];
                }
                //cout<<"dp"<<i<<j<<"="<<dp[i][j]<<" ";
            }
        }
        cout<<(dp[plen][slen]?"true":"false")<<endl;

    }
}