前言：不知不覺又斷更一天了，其實昨天就把這道題寫得差不多了，只是剛好在力扣里面看見了一種新的解法，本來想寫出來的，但是我把它推到今天了，因為太晚了，但是今天又睡懶覺了，所以我直接寫出思路，就不寫代碼了，今天在寫了這道題的題解之后，我覺得我之前寫的力扣第十題的題解相比于這道題還是太過于稚嫩了，沒有抓到主體上面，不夠通俗易懂，都是它的缺點
解題思路：
? ? ? ? 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 的是否存在字符串之中，并且它們的相對位置是否一致，就可以表明是相匹配的
以上就是本次題解了，我這個暑假要去學車，科目一的題目還沒有開始練，不知道自己暑假為什么會這么懶惰，天天不是玩云頂之弈去找虐，就是打排位去找氣受，不知道我的腦袋里面在想啥
唉，算了，算了，我已經把游戲給刪掉了，頂多每天上線打一下日活，不能再墮落下去了
提醒：紙上得來終覺淺，絕知此事要躬行
