LeetCode--44.通配符匹配
前言：不知不觉又断更一天了，其实昨天就把这道题写得差不多了，只是刚好在力扣里面看见了一种新的解法，本来想写出来的，但是我把它推到今天了，因为太晚了，但是今天又睡懒觉了，所以我直接写出思路，就不写代码了，今天在写了这道题的题解之后，我觉得我之前写的力扣第十题的题解相比于这道题还是太过于稚嫩了，没有抓到主体上面，不够通俗易懂，都是它的缺点
解题思路：
1.获取信息：
给定一个字符串和一个字符模式
字符模式中包含小写字母，？以及 *
？：可以匹配任何单个字符
* ：可以匹配任意字符序列（包括空字符序列）
要求判断字符模式是否能完全匹配字符串
2.分析题目：
在看到这道题的时候，我想到了之前写过的，力扣第十题，正则表达式
它也是给定一个字符串和字符模式，只不过字符模式中的特殊符号的功能比这道题中的要复杂一些，所以这道题可以说是一道简化后的第十题
那么，它的方法就不言而喻了，与第十题一样，是动态规划法，但我转念一想，要是方法都不怎么改变，没有多少新意，那怎么能考验自己呢？
所以我又尝试用它的核心思想写了一下递归法，但是很遗憾，在1638个示例的时候，超时了，不过我还是会讲解一下，也许可以帮助你理解
最后，我会讲解一下力扣看到的那个新方法，也很不错的
3.示例查验：
略
4.尝试编写代码：
（1）动态规划法：
思路：动态规划：用小问题来逐步推导出大问题
我们知道在面对通配符，肯定是需要考虑多种情况的，就以遇到 * 为例
遇到 * ，它就会存在两种情况，它表示空字符或者表示非空字符
表示空字符，那就无事发生
表示非空字符，那它可能表示一个字符，两个字符或者更多的字符
这些都是需要考虑的情况
实际上，动态规划并不能解决我上面说的需要考虑多种情况的难题
动态规划解决的只是，一个既定事实的未来发展而已，就比如说，它的下一步的发展是取决于上一步的确定，所以我们动态规划实行的方式如下
先说一下前提，我们肯定是要扫描字符来进行匹配的，那么以谁为主体开始扫描呢？
那肯定是字符模式了，因为字符模式中不止存在小写字母
好了，说回动态规划
以扫描字符模式为主体，会遇到三种情况
1.小写字母，比较字符串中对应位置，相同，则继续，不同，直接结束
2.？，可以匹配任意字符，直接继续
3. * ，需要考虑表示空字符和非空字符的情况
如你所见，这些判断都是默认前面的字符完全相匹配的情况下，才可以这么判断
并且，在遇到 * ，动态规划就显得有些手足无措了，所以单纯的动态规划不能解决遇到 * 的情况
所以，我们如果是个机器，要处理这样的问题，我们只会遍历完所有的情况，让所有的情况都用动态规划走一遍，那么只要有一条走得通，那么就说明可以匹配
其实核心不怎么在动态规划，而是这个遍历完所有的情况的步骤
我们在遇到 * 时，就依次遍历，* 表示零个字符，一个字符，两个字符等多个字符的情况，只要有一条走得通，那么就表示匹配成功
以下是完整代码
class Solution {
public:bool isMatch(string s, string p) {//代码跟力扣第十题大致没有多少区别，就不进行注释了int m=s.size();int n=p.size();vector<vector<bool>>dp(m+1,vector<bool>(n+1,false));dp[m][0]=false;dp[0][0]=true;for(int j=1;j<=n;j++){if(p[j-1]=='*')dp[0][j]=true;else break;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(p[j-1]=='*'){dp[i][j]=dp[i][j-1]||dp[i-1][j];}else if(p[j-1]=='?'){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=(s[i-1]==p[j-1])&&dp[i-1][j-1];}}}return dp[m][n];}
};（2）递归法：
思路：上面我们说了遇到星号，要依次遍历每种情况，我就想到用递归这种方便推行多种情况的方法，来对每种情况进行遍历
但是很遗憾，如我上面所说，在第1638个示例的时候，超时了
以下是完整代码
class Solution {
public:bool isMatch(string s, string p) {return GetRes(s,p,0,0,s.size(),p.size());}
private:bool GetRes(string&s,string&p,int i,int j,int m,int n){if(j==n)return i==m;if(i==m){while(j<n&&p[j]=='*')j++;return j==n;}if(p[j]=='*'){return GetRes(s,p,i,j+1,m,n)||GetRes(s,p,i+1,j,m,n);}else if(p[j]=='?'){return GetRes(s,p,i+1,j+1,m,n);}else{if(s[i]==p[j]){return GetRes(s,p,i+1,j+1,m,n);}else return false;}}
};（3）贪心算法：
这是我在力扣上面看到的题解，比较惊奇，我一开始没有想出来，故而记录下来
思路：在字符模式中，比较麻烦的就是碰到星号，其他的符号不值一提
如果没有星号，这道题会变得特别简单，所以，有没有办法去无视星号呢？
当然有，星号出现零次的情况不用考虑，特别简单，就直接说星号出现非零次的情况
那么字符模式的样式，差不多就是 " xxx * xxx * xxx * xxx "等样式
因为星号可以表示任意字符序列，所以，我们只用判断那些 xxx 的是否存在字符串之中，并且它们的相对位置是否一致，就可以表明是相匹配的
以上就是本次题解了，我这个暑假要去学车，科目一的题目还没有开始练，不知道自己暑假为什么会这么懒惰，天天不是玩云顶之弈去找虐，就是打排位去找气受，不知道我的脑袋里面在想啥
唉，算了，算了，我已经把游戏给删掉了，顶多每天上线打一下日活，不能再堕落下去了
提醒：纸上得来终觉浅，绝知此事要躬行