深度解析「正則表達式匹配」：從暴力解法到動態規劃
- 2019 年 11 月 26 日
- 筆記
題目描述
給你一個字元串 s 和一個字元規律 p，請你來實現一個支援 '.' 和'*' 的正則表達式匹配。
'.' 匹配任意單個字元 '*' 匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋 整個 字元串 s 的，而不是部分字元串。
說明:
s可能為空，且只包含從a-z的小寫字母。p可能為空，且只包含從a-z的小寫字母，以及字元.和*。
示例 1:
輸入: s = "aa" p = "a" 輸出: false 解釋: "a" 無法匹配 "aa" 整個字元串。
示例 2:
輸入: s = "aa" p = "a*" 輸出: true 解釋: 因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這裡前面的元素就是 'a'。因此，字元串 "aa" 可被視為 'a' 重複了一次。
示例 3:
輸入: s = "ab" p = ".*" 輸出: true 解釋: ".*" 表示可匹配零個或多個（'*'）任意字元（'.'）。
示例 4:
輸入: s = "aab" p = "c*a*b" 輸出: true 解釋: 因為 '*' 表示零個或多個，這裡 'c' 為 0 個, 'a' 被重複一次。因此可以匹配字元串 "aab"。
示例 5:
輸入: s = "mississippi" p = "mis*is*p*." 輸出: false
題目解析
這道題其實是要實現 Regular Expression 裡面的兩個符號，一個是 '.'，另一個是 '*'， 前者表示可以 match 任意一個字元，後者表示其前面的字元可以重複零次或者多次。
題目的難點其實是在於 * 上面，如果沒有這個 *，題目會變得非常簡單，這裡說一下題目的兩個隱含條件：
- 一個就是 * 不會出現在字元串的開頭
- 另外一個是 * 前面不能是 *，比如 "a * * b" 就不行
當然你也可以把這兩個隱含條件當作一個來看，不管如何，我們的程式碼實現必須建立在這個基礎之上，否則，case 考慮多了，題目將無從下手。
解法一：遞歸暴力求解
遞歸方式的暴力深度優先搜索求解方法往往是搜索問題的萬金油，這裡你只需要簡單的考慮兩件事情，一是這個問題是否可以劃分為子問題，二是每個子問題有幾種狀態，就是在當前考慮的問題下，一共有多少種可能性。
知道了這兩點後，對於每個子問題的每一個狀態遞歸求解就行。
上面說的可能有點抽象，結合這個題目來做例子，這裡的問題是，輸入一個字元串 s，以及其匹配字元串 p，要求解這兩個字元串是否匹配。
我們首先考慮這個字元串比較的問題能不能劃分為一個個的子問題，你發現字元串是可以劃分成為一個個字元的，這樣字元串比較的問題就會變成字元的比較問題，這樣一來，我們就可以把問題看成，決定 s[i,…n] 是否能夠匹配 p[j,…m] 的條件是子問題 s[i+1,…n] 能不能夠匹配 p[j+1,…m]，另外還要看 s[i] 和 p[j] 是否匹配，但是這裡的當前要解決的問題是 s[i] 和 p[j] 是否匹配，只有這一點成立，我們才有繼續遞歸去看 s[i+1,…n] 是匹配 p[j+1,…m]，注意這裡我說 s[i] p[j]， 並不表示說當前就只用考慮這兩個字元之間匹不匹配，它只是用來表示當前問題，這個當前問題也許只需要比較一個字元，也許要比較多個，這就引申出了前面提到的第二點，我們還需要考慮當前問題中的狀態。
對於字元串 s 來說，沒有特殊字元，當前問題中字元只會是字母，但是對於 p 來說，我們需要考慮兩個特殊符號，還有字母，這裡列舉所有的可能，如果說當前的子問題是 s[i,…n] 和 p[j…m]:
- s[i] == p[j]，子問題成立與否取決於子問題 s[i+1,…n] 和 p[j+1,…m]
- p[j] == '.'，子問題成立與否取決於子問題 s[i+1,…n] 和 p[j+1,…m]
- p[j+1] == '*'，s[i] != p[j]，子問題成立與否取決於子問題 s[i,…n] 和 p[j+2,…m]
- p[j+1] == '*'，s[i] == p[j]，子問題成立與否取決於子問題 s[i+1,…n] 和 p[j,…m]
這裡我解釋下第三種情況，之前在題目描述里說過，p 的起始字元不可能是 *，也就是說 * 的前面必須有字母，根據定義，這裡我們可以把 * 的前面的元素個數算作是零個，這樣我們就只用看，s[i,…n] 和 p[j+2,…n] 是否匹配，如果算作一個或者多個，那麼我們就可以看 s[i+1,…n] 和 p[j,…m] 是否成立，當然這個的前提是 p[j] == s[i] 或者 p[j] == '.'， 我們可以結合程式碼來看看
class Solution { public boolean isMatch(String s, String p) { if (s.equals(p)) { return true; } boolean isFirstMatch = false; if (!s.isEmpty() && !p.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) { isFirstMatch = true; } if (p.length() >= 2 && p.charAt(1) == '*') { // 看 s[i,...n] 和 p[j+2,...m] 或者是 s[i+1,...n] 和 p[j,...m] return isMatch(s, p.substring(2)) || (isFirstMatch && isMatch(s.substring(1), p)); } // 看 s[i+1,...n] 和 p[j+1,...m] return isFirstMatch && isMatch(s.substring(1), p.substring(1)); } }
上面的實現之所以被稱為暴力求解是因為子問題的答案沒有被記錄，也就是說如果當前要用到之前的子問題的答案，我們還得去計算之前計算過的子問題。
解法二：記憶化搜索
上面的暴力解法是因為沒有記錄答案，記憶化搜索是在 「傻搜」 的基礎之上添加 「記事本」。這裡我把遞歸的方向給改變了，當然這不是必要的，主要想說明，對於遞歸來說，從後往前考慮和從前往後考慮都是可行的。
我們假設當前問題是考慮 s 的第 i 個字母，p 的第 j 個字母，所以這時的子問題是 s[0…i] 和 p[0…j] 是否匹配：
- p[j] 是字母，並且 s[i] == p[j]，當前子問題成立與否取決於子問題 s[0…i-1] 和 p[0…j-1] 是否成立
- p[j] 是 '.'，當前子問題成立與否取決於子問題 s[0…i-1] 和 p[0…j-1] 是否成立
- p[j] 是字母，並且 s[i] != p[j]，當前子問題不成立
- p[j] 是 '*'，s[i] == p[j – 1]，或者 p[j – 1] == '.'， 當前子問題成立與否取決於子問題 s[0…i-1] 和 p[0…j] 是否成立
- p[j] 是 '*'，s[i] != p[j – 1]，當前子問題正確與否取決於子問題 s[0…i] 是否匹配 p[0,…j-2]
不管是從前往後，還是從後往前，你可以看到，考慮的點都是一樣的，只是這裡我們多加了一個 「記事本」
public boolean isMatch(String s, String p) { if (s.equals(p)) { return true; } boolean[] memo = new boolean[s.length() + 1]; return helper(s.toCharArray(), p.toCharArray(), s.length() - 1, p.length() - 1, memo); } private boolean helper(char[] s, char[] p, int i, int j, boolean[] memo) { if (memo[i + 1]) { return true; } if (i == -1 && j == -1) { memo[i + 1] = true; return true; } boolean isFirstMatching = false; if (i >= 0 && j >= 0 && (s[i] == p[j] || p[j] == '.' || (p[j] == '*' && (p[j - 1] == s[i] || p[j - 1] == '.')))) { isFirstMatching = true; } if (j >= 1 && p[j] == '*') { // 看 s[0,...i] 和 p[0,...j-2] boolean zero = helper(s, p, i, j - 2, memo); // 看 s[0,...i-1] 和 p[0,...j] boolean match = isFirstMatching && helper(s, p, i - 1, j, memo); if (zero || match) { memo[i + 1] = true; } return memo[i + 1]; } // 看 s[0,...i-1] 和 p[0,...j-1] if (isFirstMatching && helper(s, p, i - 1, j - 1, memo)) { memo[i + 1] = true; } return memo[i + 1]; }
解法三：動態規劃
有了上面兩種方法和解釋作為鋪墊，我想迭代式的動態規劃應該不難理解。這裡我們不再用遞歸，而是使用 for 循環的形式，先上程式碼：
public boolean isMatch(String s, String p) { if (s.equals(p)) { return true; } char[] sArr = s.toCharArray(); char[] pArr = p.toCharArray(); // dp[i][j] => is s[0, i - 1] match p[0, j - 1] ? boolean[][] dp = new boolean[sArr.length + 1][pArr.length + 1]; dp[0][0] = true; for (int i = 1; i <= pArr.length; ++i) { dp[0][i] = pArr[i - 1] == '*' ? dp[0][i - 2] : false; } for (int i = 1; i <= sArr.length; ++i) { for (int j = 1; j <= pArr.length; ++j) { if (sArr[i - 1] == pArr[j - 1] || pArr[j - 1] == '.') { // 看 s[0,...i-1] 和 p[0,...j-1] dp[i][j] = dp[i - 1][j - 1]; } if (pArr[j - 1] == '*') { // 看 s[0,...i] 和 p[0,...j-2] dp[i][j] |= dp[i][j - 2]; if (pArr[j - 2] == sArr[i - 1] || pArr[j - 2] == '.') { // 看 s[0,...i-1] 和 p[0,...j] dp[i][j] |= dp[i - 1][j]; } } } } return dp[sArr.length][pArr.length]; }
這裡我說一下前面的 DP 數組的初始化，因為需要考慮空串的情況，所以我們 DP 數組大小多開了 1 格。dp[0][0] = true 因為兩個空串是匹配的，緊接著下面一行的 for 循環是為了確保空串和 p 的一部分是匹配，比如 s = ""，p = "a*b"，那麼這裡 dp[0][2] = true，也就是 s[0,0]和p[0,2] 是匹配的，注意和之前不一樣的是這裡的 0 代表空串。
字元串匹配類動態規劃的總結和思考
一般來說，對於字元串匹配的問題中，輸入參數都會有兩個字串，如果確定了這道題的問題是可以分解成一系列子問題，那麼就可以考慮使用動態規劃求解，可以根據區間來定義狀態，一般來說只需要考慮頭區間或者是尾區間，這道題中的動態規劃解法，我們就是考慮了頭區間，s[0,…i]和p[0,…j] 是否匹配記錄在 dp[i+1][j+1] 中，如果你選擇尾區間的話，那麼遍歷的方式需要從後往前，就和之前講解的記憶化搜索一樣。所以一般的字元串匹配的動態規劃的 DP 數組都是二維的，當然也有特例。個人覺得確定了考慮的區間和遍歷方向，至少來說在動態規劃狀態方程的推導上會清晰不少。
接下來就是重點的部分，遞推方程的推導，這裡沒有特別多的技巧，還是那句話，唯手熟爾，無他，要說重點的話，還是在確定當前子問題和前面子問題的聯繫上吧，或者你可以這樣想 「當前考慮的子問題在什麼情況下會變成前面求解過的子問題」。
還是拿這道題舉例，上面的 DP 解法我們從前往後遍歷，在考慮子問題 s[0,…i]和p[0,…j] 是否匹配，如果拿掉 s[i] 和 p[j]，這個問題就會變成前面求解過的子問題 s[0,…i-1]和p[0,…j-1]，如果只拿掉 s[i]，這個問題就會變成前面求解過的子問題 s[0,…i-1]和p[0,…j]，如果只拿掉 p[j-1,j]，這個問題就會變成前面求解過的子問題 s[0,…i]和p[0,…j-2]，至於為什麼有些可以拿掉，有些不能，那這個只能根據題意來分析了，相信通過前面的分析應該不難理解。
結合上面的分析，這裡列了一些字元串匹配類動態規劃的一些注意事項：
- 注意考慮是否需要考慮空串的情況，如果是的話，一般 DP 數組需要多開一格
- 在考慮遞推方程前，確定子問題的區間和遍歷方向
- 在思考遞推方程的時候，重點思考當前子問題怎麼變成之前求解過的子問題
以上就是全部，希望對於你理解這道題，或者說是理解字元串匹配類動態規劃有所幫助。
