今天是LeetCode專題的第24篇文章，我們一起來看LeetCode的44題——Wildcard Matching，這是一道Hard難度的問題，會稍稍有點難，但是好消息是沒有出現我們之前沒見過的算法。
題意很簡單，給定兩個字符串s和p，其中s是母串，p是模式串。簡單解釋一下這兩個概念，這兩個概念一般出現在字符串匹配的問題當中。有些同學可能不太理解，我們打個不恰當的比方，我們可以把母串想象成鎖，把模式串想象成鑰匙。一些萬能鑰匙可以打開多把鎖，也就是說鑰匙是可以變化的，鎖是固定的。我們要判斷的就是模式串能不能匹配上母串，也就是鑰匙能不能打開鎖。
在模式串p當中可能出現兩種特殊字符，一種是?，它表示匹配任何單一字符。還有一種是*，它表示匹配任何一串字符，包括空字符串。所以這個*看起來非常強大，一個可以任意匹配。但是這題當中有一個限制，s和p必須要是完全匹配，不能是部分匹配。也就是說p當中的所有字符都要用上，舉個例子，s串是aab，p串是*c。雖然*就足夠匹配s串的所有內容，但是由於之後跟了一個c沒有用上，所以不能算是合法匹配。
為了簡化說明，我們用si表示s串的第i個字符，pi表示p串的第i個字符。
搜索
我們還是先從簡單的方法構思，最先思考暴力的解法，很容易發現在這道題當中沒有辦法簡單粗暴地暴力計算。原因也很簡單，因為當出現*這個符號的時候，
我們不知道它究竟應該匹配多長的字符串。可以是0，也可以是長度任意一隻匹配到結尾。為了解決這個問題，最好的辦法就是都試一試，枚舉一下*這個符號應該匹配的長度。但是由於*的數量可能不止一個，如果出現多個的話，由於前後會互相影響，並且前後之間存在順序，也就是說*這個符號如何匹配的決策不是一起做的，而是有先後的。就和八皇后當中的皇后不是一起擺放的，而是有先後順序的，如果我們把*看成是皇后，其實這已經是比較明顯的搜索問題了。
如果想通了，把這題當成是搜索問題來解決的話，其實並不算困難，其實就是簡單的枚舉。
我們搜索s和p串匹配的位置，我們用si表示s串當前需要匹配的字符，pi表示p串當前需要匹配的字符。如果pi位置的字符不是*，那麼情況比較有限，我們只需要判斷上下界以及是否匹配即可。如果pi的位置是*，那麼情況會複雜一些，因為*的出現意味著三種決策。
第一種決策是不使用*來匹配當前位置的si，在這種情況下意味著我們拋棄這個*，但是si還是沒有找到匹配的對象，所以si不能移動，從這點出發，我們可以得到下一個轉移到的位置是si，pi+1。即p當中的指針移動了一位，但是s中的指針保持不動，等待繼續匹配。
第二種決策是只匹配當前的si，不再匹配si之後的內容。在這種情況下，我們只需要把*當成是一個正常的字符處理就好了，那麼我們應該轉移到的位置是si+1，pi+1。也就是說s和p當中的指針各自移動了一位。
第三種決策是*不止匹配當前的si，並且還會繼續往下匹配，在這種情況下我們需要保持pi的位置不動，只移動si，也就是說我們會轉移到si+1和pi。
但是我們仔細分析一下，會發現其實這三種情況是可以合併的。在第二種情況中，我們只匹配當前位置，其實這等價於我們在當前位置執行第三種策略，在轉移之後的位置執行策略1。
舉個例子：比如s串是abc，p串是a*c。我們在匹配第二個字符的時候，執行策略3，於是跳轉到2, 1。也就是si是c，pi仍然是*，這個時候我們再執行策略1，則會跳轉到2，2，和我們在一開始的時候執行策略2是一致的。這樣在*出現很多的時候可以減少決策過程，起到加速的作用。
最後，由於這是一道搜索答案存不存在的問題，並不需要我們找到所有的解。在這種情況下，使用bfs會比dfs效率更高，但遺憾的是這兩種方法我都試過了，都無法通過，因為會超時。可能這是Python的原因（解釋型語言執行效率低），因為我用C++是可以過的。
雖然過不了，但是思路是對的，不介意的話可以看下代碼：
動態規劃
雖然上面的方法無法通過，但其實已經給了我們很多啟發了，如果我們把上面提到的si和pi看成是狀態的話，雖然我們是用bfs實現的，但本質上已經是動態規劃的思想了。
在一些動態規劃的問題當中，我們也是通過隊列來維護狀態的。我們會將合法的狀態全部存儲在隊列當中，當我們通過狀態和決策轉移到新的合法狀態的時候，我們繼續插入隊列。所以從這個角度來說動態規劃和搜索問題本質是類似的，或者更準確一點說動態規劃只是一種思想，它實現的載體可以多種多樣，既可以是使用數組遞推，也可以是使用數據結構維護狀態。這一點非常重要，也是我們動態規劃進階的基礎。
我們為什麼會超時？
如果我們把剛才搜索的思路看成是動態規劃的話，會發現這是一個順推的動態規劃。簡單介紹一下，動態規劃的狀態和轉移雖然每題當中都不盡相同，但是整體的思路只有兩種。一種叫做順推，一種是逆推。
在順推思路當中，我們記錄所有合法的狀態，然後從合法的狀態出發，通過決策進行轉移，將轉移得到的狀態記錄下來留待後續繼續轉移。如果我們把這些狀態串聯起來的話，會發現我們是順著一個邏輯上的順序執行的，所以稱為順推。逆推則恰恰相反，我們遍歷未知的狀態，通過狀態之間的轉移關係，探索它的源頭，從而確定當前未知狀態的結果。也就是說一個是從已知到未知，另一個是先獲得未知再探索它已知的來源。
為什麼在這題當中順推不行呢？因為當*出現的時候，我們繼續往下推進的狀態當中仍然有*。比如當我們決定使用*來匹配si的時候，我們會轉移到si+1，pi狀態。在後序的狀態當中同樣包含了*，又會面臨更多的狀態。這些狀態中間很多會出現重疊，並且這些重疊的狀態當中有很多是剪枝也無法解決的，比如p串當中一連串的*。這個時候我們就可以換換角度思考一下逆推了。
常規套路，我們用dp[i][j]記錄s[:i+1]和p[:j+1]匹配的狀態，那麼這個dp[i][j]可能是哪些狀態轉移過來的呢？其實非常有限，如果si和pi能夠匹配，那麼它可以從dp[i-1][j-1]轉移過來。如果不匹配，我們需要判斷一下pi是否是*。如果是的話，則有兩種情況，一種是*匹配空，把si交給pi-1，所以可以從dp[i][j-1]轉移得到。另一種是匹配si，由於*可以匹配的數量不止一個，所以這時候可以從dp[i-1][j]轉移得到。由於每個i，j的狀態來源非常有限，只有有限的幾種，所以我們完全可以枚舉所有的i，j進行倒推，這樣的複雜度就是O(nm)，是完全可控的。
把上面這段話梳理清楚的話，這就是一個非常明顯的動態規劃問題了。
我們來看代碼，從代碼當中獲得更多細節吧。
這段代碼雖然短，但是其中的細節不少，包括下標以及邊界等條件。所以建議大家理解思路之後上手寫過再來對照代碼進行思考，相信會有更多收穫。因為很多細節可能是需要看到了錯誤的case進行思考之後才會明白，這也是LeetCode當中一個比較好的點，可以看到測試數據，可以知道自己錯在哪裡。
今天的文章就是這些，另外在次條當中分享了vscode當中LeetCode的插件使用方法，感興趣的同學不要錯過，最後，祝大家刷題愉快。
如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
