LeetCode10 Hard，實現字元串正則匹配
- 2020 年 3 月 5 日
- 筆記
點擊上方藍字，和我一起學技術。
Link
https://leetcode.com/problems/regular-expression-matching/
Difficulty
Hard
Description
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character. '*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like.or*.
題意
這道題屬於典型的人狠話不多的問題，讓我們動手實現一個簡單的正則匹配演算法。不過為了降低難度，這裡需要匹配的只有兩個特殊符號，一個符號是'.'，表示可以匹配任意的單個字元。還有一個特殊符號是'*'，它表示它前面的符號可以是任意個，可以是0個。
題目要求是輸入一個母串和一個模式串，請問是否能夠達成匹配。
Example 1:
Input: s = "aa" p = "a" Output: false ## Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa" p = "a*" Output: true ## Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab" p = ".*" Output: true ## Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input: s = "aab" p = "c*a*b" Output: true ## Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Output: false
這題要求的是完全匹配，而不是包含匹配。也就是說s串匹配完p串之後不能有剩餘，比如剛好完全匹配才行。明確了這點之後，我們先來簡化操作，假設不存在'*'這個特殊字元，只存在'.'，那麼顯然，這個簡化過後的問題非常簡單，我們隨便就可以寫出程式碼：
def match(s, p): n = len(s) for i in range(n): if s[i] == p[i] or p[i] == '.': continue return False return True
我們下面考慮加入'*'的情況，其實加入'*'只會有一個問題，就是'*'可以匹配任意長度，如果當前位置出現了'*'，我們並不知道它應該匹配到哪裡為止。我們不知道需要匹配到哪裡為止，那麼就需要進行搜索了。也就是說，我們需要將它轉換成一個搜索問題來進行求解。我們試著用遞歸來寫一下：
def match(s, p, i, j): # 當前位置是否匹配 flag = s[i] == p[j] or p[j] == '.' # 判斷p[j+1]是否是*，如果是那麼說明p[j]可以跳過匹配 if j+1 < len(p) and p[j+1] == '*': # 兩種情況，一種是跳過p[j]，另一種是p[j]繼續匹配 return match(s, p, i, j+2) or (flag and match(s, p, i+1, j)) else: # 如果沒有*，只有一種可能 return flag and match(s, p, i+1, j+1)
這段程式碼的精髓在於，由於'*'之前的符號也可以是0個，所以我們不能判斷當前位置是否會是'*'，而要判斷後面一個位置是否是'*'。這句話看起來有些像是繞口令，但是卻是這道題的精髓，如果看不懂的話，可以結合一下程式碼思考。
總之，就是以出否出現'*'為基點，分情況進行遞歸即可。
從程式碼上來看算上注釋才12行，可是將這裡面的關係都梳理清楚，並不容易。還是非常考驗基本功的，需要對遞歸有較深入的理解才行。不過，這並不是最好的方法，因為你會發現有很多狀態被重複計算了很多次。這也是遞歸演算法經常遇到的問題之一，要解決倒也不難，我們很容易發現，對於固定的i和j，答案是固定的。那麼，我們可以用一個數組來存儲所有的i和j的情況。如果當前的i和j處理過了，那麼直接返回結果，否則再去計算。
這種方法稱作記憶化搜索，說起來複雜，但是實現起來只需要加幾行程式碼：
memory = {} def match(s, p, i, j): if (i, j) in memory: return memory[(i, j)] # 當前位置是否匹配 flag = s[i] == p[j] or p[j] == '.' # 判斷p[j+1]是否是*，如果是那麼說明p[j]可以跳過匹配 if j+1 < len(p) and p[j+1] == '*': # 兩種情況，一種是跳過p[j]，另一種是p[j]繼續匹配 ret = match(s, p, i, j+2) or (flag and match(s, p, i+1, j)) else: # 如果沒有*，只有一種可能 ret = flag and match(s, p, i+1, j+1) memory[(i, j)] = ret return ret
如果你對動態規劃足夠熟悉的話，想必也應該知道，記憶化搜索本質也是動態規劃的一種實現方式。但同樣，我們也可以選擇其他的方式實現動態規劃，就可以擺脫遞歸了，相比於遞歸，使用數組存儲狀態的遞推形式更容易理解。
我們用dp[i][j]存儲s[:i]與p[:j]是否匹配，那麼根據我們之前的結論，如果p[j-1]是'*'，那麼dp[i][j]可能由dp[i][j-2]或者是dp[i-1][j]轉移得到。dp[i][j-2]比較容易想到，就是'*'前面的字元作廢，為什麼是dp[i-1][j]呢？這種情況是代表'*'連續匹配，因為可能匹配任意個，所以必須要匹配在'*'這個位置。
舉個例子：
s = 'aaaaa' p = '.*'
在上面這個例子里，'.'能匹配所有字元，但是問題是s中只有一個a能匹配上。如果我們不用dp[i-1][j]而用dp[i-1][j-1]的話，那麼是無法匹配aa或者aaa這種情況的。因為這幾種情況都是通過'*'的多匹配能力實現的。如果還不理解的同學， 建議仔細梳理一下它們之間的關係。
我們用數組的形式寫出程式碼：
def is_match(s, p): # 為了防止超界，我們從下標1開始 s = '$' + s p = '$' + p n, m = len(s), len(p) dp = [[False for _ in range(m)] for _ in range(n)] dp[0][0] = True # 需要考慮s空串匹配的情況 for i in range(n): for j in range(1, m): # 標記當前位置是否匹配，主要考慮s為空串的情況 match = True if i > 0 and (s[i] == p[j] or p[j] == '.') else False # 判斷j位置是否為'*' if j > 1 and p[j] == '*': # 如果是，只有兩種轉移的情況，第一種表示略過前一個字元，第二種表示重複匹配 dp[i][j] = dp[i][j-2] or ((s[i] == p[j-1] or p[j-1] == '.') and dp[i-1][j]) else: # 如果不是，只有一種轉移的可能 dp[i][j] = dp[i-1][j-1] and match return dp[n-1][m-1]
這題的程式碼並不長，算上注釋也不過20行左右。但是當中對於題意的思考，以及對演算法的運用很高，想要AC難度還是不低的。希望大家能夠多多揣摩，理解其中的精髓，尤其是最後的動態規劃解法，非常經典，推薦一定要弄懂。當然如果實在看不明白也沒有關係，在以後的文章，我會給大家詳細講解動態規劃演算法。
今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支援是我最大的動力。
