力扣题解（通用符匹配）

44. 通配符匹配

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

• '?' 可以匹配任何单个字符。
• '*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

思路：

首先看题目要求，当p[j]是小写字母，则一对一匹配，当是？，则无条件匹配成功一个，当为*，则无条件匹配任意子串。这里*的效果十分强势，可以当作空串使用，也可以当作任意的字符序列，而不是单纯某一个字符的反复出现（" ","aaassbbb"等均是可以的）

dp[i][j]表示用p的0到j来表示s的0到i是否可以。对于dp的组成，需要按照p[j]的情况进行划分。

当p[j]为小写字母，仅当p[j]==s[i]时有dp[i][j]=dp[i-1][j-1]。

当p[j]为"?"，一定有有dp[i][j]=dp[i-1][j-1]。

当p[j]为"*"，需要分情况讨论，分的情况时p[j]要匹配s中从最后一个往前的多少个字符，

则dp[i][j]=dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1]|.........||dp[0][j-1]，上述为匹配0个到全部i个都被匹配的所有情况，但这部分是可以进行一定程度上的化简的，即对于匹配一个到匹配全部i个，可以看成是dp[i-1][j],即已经默认去掉一个的情况下的可能。（而且dp[i-1][j]=dp[i-1][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1]|.........||dp[0][j-1]）。

初始化：

当i为0时，则表示用p的0到j来匹配空串，仅有p的前j个全是*才为true。

对于j为0，除了i也为0时，空串均无法表示s的0到i的子串，因此全为false，不用管。

class Solution { public:     bool isMatch(string s, string p) {       int n1=s.size();       int n2=p.size();       vector<vector<bool>>dp(n1+1,vector<bool>(n2+1,false));            dp[0][0]=true;       int k=0;       while(p[k]=='*')       {          for(int i=0;i<=n1;i++)         dp[i][k+1]=true;         k++;       }       if(n1==0)       {         for(auto e:p)         {             if(e!='*')             return false;         }         return true;       }       //chushihua           for(int i=1;i<=n1;i++)       {         for(int j=1;j<=n2;j++)         {             if(p[j-1]=='?'||p[j-1]==s[i-1])             {               dp[i][j]=dp[i-1][j-1];             }             else if(p[j-1]=='*')             {                                dp[i][j]=dp[i-1][j]||dp[i][j-1];//优化             }         }       }        return dp[n1][n2];     } };