這節課將分析三道比較難的題目，希望能幫助大家拓寬解題的思路。主要內容包括： * 正則表達式匹配 * 柱狀圖中的最大矩形 * 實現 strStr() 函數 #### 例題分析一 LeetCode 第 10 題，正則表達式匹配：給你一個字符串 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 ``` 解釋：'p'與'i'無法匹配。 **解題思路** 不要害怕，這道題只要求實現正則表達式里的兩個小功能。 **判斷 s 和 p 匹配** 舉例：給定兩個字符串 s 和 p，判斷 s 和 p 是否匹配。 解法：s 和 p 必須要相等。定義兩個指針 i 和 j，分別指向 s 和 p 的第一個字符，然后逐個去比較，一旦發現不相等，就立即知道 s 和 p 不匹配。 此時，假設 s 字符串的長度為 m，p 字符串的長度為 n，s 和 p 匹配的條件就是 s 和 p 從頭到尾一直匹配，即 i == m 同時 j == n 是 s 和 p 匹配的唯一條件。 **點匹配符 '.'** '.' 匹配任意單個字符，首先要明確的是，它是一一對應關系，和 '*' 匹配符不一樣。舉例說明如下。 ``` 輸入: s = "leetcode" p = "l..tc..e" 輸出: true ``` 因為 '.' 可以匹配任何字符，即，一旦遇上了 '.' 匹配符，可以讓 i 指針和 j 指針同時跳到下一個位置。 **星匹配符?'*'?** '*' 匹配符較難，先要理解這個星匹配符的定義。題目“ '*' 匹配零個或多個前面的那一個元素”中包含三個重要的信息： 1. 它匹配的是 p 字符串中，該 '*' 前面的那個字符。 2. 它可以匹配零個或多個。 3. '*' 匹配符前面必須有一個非星的字符。 因此，在分析 '*' 匹配符的時候，一定要把 '*' 以及它前面的一個字符看作為一個整體， '*' 不能單獨作為一個個體來看（例如點匹配符）。例如，p 字符串是 a *，則把 (a*) 當作一個整體來看。 ?? 對 p 字符串說明如下。 * p 可以表示空字符串，因為 '*' 可以匹配 0 個前面的字符，即當有 0 個 a 的時候，為空字符串。 * a* 還能匹配一個 a，兩個 a，三個 a，一直到無窮個 a。 * 當 p 等于 '.*' 的時候，可以表示一個空字符串，也可以表示一個點，兩個點，三個點，一直到無窮個點。即它可以表示任何長度的一段字符串，包括空串。 舉例說明 ``` 輸入： s = "aaabcd" p = "ac*a*b.." ``` 1. 用兩個指針 i 和 j 分別指向 s 和 p 的開頭。 2. 在 p 字符串里，a 的下一個字符是 c，不是 '*'，比較 s[i] 和 p[j]。因為它們都是字符 a，所以這個位置匹配正確，i 和 j 同時指向下一個。此時 j 的下一個字符是 '*'，要將 c* 當作一個整體去看待。? ??? ? ? 3. 將 c* 看成是空字符，p 如下所示。 ? ? 4. 若匹配中不一致即 c* 不能當作空字符串，則當作一個 c 字符，此時 p 如下。 5. 若不行，則看作兩個 c。 以此類推，應用了回溯的思想。 對于將 c* 作為空字符串的情況。每一次，都要看看當前 j 指向的字符的下一個是不是 '*'。如果是 '*'，就要作為整體考慮。很明顯，a 的下一個字符是 '*'。 ? 同樣，先將 a* 作為空字符串看待。此時，a != b，兩個字符串不匹配，因此回溯.現在將 a* 看成是一個 a，此時 a = a，兩個位置的字符匹配。 j 的下一個字符不是 '*'，而是點號，比較 s[i] 和 p[j]，發現 a != b。于是再次回溯，將 a* 看成是兩個 a，回到剛才的位置。 最后遇到了兩個點號，由于點號可以匹配任何字符，因此可以直接忽略。i 和 j 同時往前一步，再次遇到了點號。i 和 j 繼續往前一步。 ? 此時，i 和 j 都已經同時結束了各自的遍歷，表明 s 和 p 是匹配的。 > 提示：重點是把這種回溯的思想掌握好。對于這道題，可以采用遞歸的寫法，也可以采用動態規劃的寫法。 * [ ] 遞歸法一 一開始，用兩個指針 i 和 j 分別指向字符串 s 和 p 的第一個字符，當我們發現它們指向的字符相同時，我們同時往前一步移動指針 i 和 j。 接下來重復進行相同的操作，即，若將函數定義為 isMatch(String s, int i, String p, int j) 的話，通過傳遞 i 和 j，就能實現重復利用匹配邏輯的效果。 當遇到點匹配符的時候，方法類似。 來看看當遇到星匹配符的情況，舉例說明如下。要不斷地用 a* 去表示一個空字符串，一個 a，兩個 a，一直到多個 a…… 當 a* 表示空字符串的時候，i 和 j 應該如何調整呢？此時 i 保持不變，j+2，遞歸調用函數的時候，變成 isMatch(s, i, p, j + 2)。 此時，指向的字符和 j 指向的字符不匹配，于是回溯，回到原來的位置。11:57 用 a* 去表示一個 a，i 指向的字符與 a 匹配，那么 i+1。指針 j，已經完成了用 a* 去表示一個 a 的任務，接下來要指向 b，調用的時候應該是 isMatch(s, i + 1, p, j + 2)。 i 指向的字符和 j 指向的字符不匹配，又進行回溯，但是不用回到最開始的位置。已知用 a* 去表示空字符串不行，表示一個 a 也不行，那么嘗試兩個 a 字符，于是，i 再往前一步，用 a* 去匹配兩個 a，i 就到了 b 的位置上，調用的時候就是 isMatch(s, i + 2, p, j + 2)。 不斷地這樣操作，一旦遇到了 '*' 組合，就不斷地嘗試，直到最后滿足匹配；或者嘗試過所有的可能還是不行則表示 s 和 p 無法匹配。 代碼實現 根據上面的思路，一起來寫遞歸的實現。主體函數如下。 ``` boolean?isMatch(String?s,?String?p)?{ ????if?(s?==?null?||?p?==?null)?{ ????????return?false; ????} ???? ????return?isMatch(s,?0,?p,?0); } ``` 主體函數非常簡單，一開始做簡單的判斷，只要 s 和 p 有一個為 null，就表示不匹配。 > 注意：面試的時候，一定要注意對這些基本情況的考量，千萬不要認為輸入的值都是有效的。 接下來實現遞歸函數。 ``` boolean?isMatch(String?s,?int?i,?String?p,?int?j)?{ ????int?m?=?s.length(); ????int?n?=?p.length(); ?? ????//?看看pattern和字符串是否都掃描完畢 ????if?(j?==?n)?{ ????????return?i?==?m; ????} ?? ????//?next?char?is?not?'*':?必須滿足當前字符并遞歸到下一層 ????if?(j?==?n?-?1?||?p.charAt(j?+?1)?!=?'*')?{ ????????return?(i?<?m)?&&? ????????????(p.charAt(j)?==?'.'?||?s.charAt(i)?==?p.charAt(j))?&&? ????????????isMatch(s,?i?+?1,?p,?j?+?1); ????} ?? ????//?next?char?is?'*',?如果有連續的s[i]出現并且都等于p[j]，一直嘗試下去 ????if?(j?<?n?-?1?&&?p.charAt(j?+?1)?==?'*')?{ ????????while?((i?<?m)?&&?(p.charAt(j)?==?'.'?||?s.charAt(i)?==?p.charAt(j)))?{ ????????????if?(isMatch(s,?i,?p,?j?+?2))?{ ????????????????return?true; ????????????} ????????????i++; ????????} ????} ?? ????//?接著繼續下去 ????return?isMatch(s,?i,?p,?j?+?2); } ``` 1. 函數接受四個輸入參數，s 字符串，p 字符串，i 指針，j 指針。 2. 開始時計算 s 字符串和 p 字符串的長度，分別記為 m 和 n。 3. 當 j 指針遍歷完了 p 字符串后，可以跳出遞歸，而 i 也剛好遍歷完，說明 s 和 p 完全匹配。 4. 判斷 j 字符的下一個是不是 '*'，不是，則遞歸地調用 isMatch 函數，i + 1，j + 1。 5. 若是，則不斷地將它和 '*' 作為一個整體，分別去表示空字符串，一個字符，兩個字符，依此類推。如果其中一種情況能出現 s 和 p 的匹配，就返回 true。 6. while 循環是整個遞歸算法的核心，前提條件如下。 i 指向的字符必須要能和 j 指向的字符匹配，其中 j 指向的可能是點匹配符。 若無法匹配，i++，即用 '*' 組合去匹配更長的一段字符串。 當 i 字符和 j 字符不相同，或者 i 已經遍歷完了 s 字符串，同時 j 字符后面跟著一個 '*'的情況，只能用 '*'組合去表示一個空字符串，然后遞歸下去。 * [ ] 遞歸法二 上法是從前往后進行遞歸地調用，現在從后往前地分析這個問題。例如： ``` s = "aaabcd" p = "a*b.d" ``` 實現過程如下所示。 1. p 字符串的最后一個字符 d 必須要和 s 字符串的最后一個字符相同，才能使 p 有可能與 s 匹配，那么當它們都相同的時候，問題規模也縮小。 2. p 字符串的最后一個字符不是 '*'，而是點號。它可以匹配 s 字符串里的任意一個字符，且它是最后一個，所以對應的就是 s 字符串里的 c，很明顯互相匹配，繼續縮小問題規模。 3. 同樣，b 不是 '*'，比較它與 s 字符串的最后一個字符是否相同，是，則繼續縮小問題規模。 4. 遇到 '*'，'*'可以表示一個空字符串，與前一個字符表示空字符串的時候，將問題變成了判斷兩個字符串是否匹配，其中，s 等于 aaa，而 p 是空字符串，很明顯不能匹配。 5. 用 a* 去表示一個 a。 6. p 的最后一個還是 '*'，用同樣的策略。 7. 繼續用 a* 去表示一個 a。 8. 用 a* 去表示空字符串。 9. 最后 s 和 p 都變成了空字符串，互相匹配。 代碼實現 主函數代碼如下。 ``` boolean?isMatch(String?s,?String?p)?{ ????if?(s?==?null?||?p?==?null)?return?false; ????return?isMatch(s,?s.length(),?p,?p.length()); } ``` 在主函數里，進行一些簡單基礎的判斷，如果 s 和 p 有一個是 null，則返回 false。 遞歸函數代碼如下。 ``` boolean?isMatch(String?s,?int?i,?String?p,?int?j)?{ ????if?(j?==?0)?return?i?==?0;? ????if?(i?==?0)?{ ????????return?j?>?1?&&?p.charAt(j?-?1)?==?'*'?&&?isMatch(s,?i,?p,?j?-?2); ????} ?? ????if?(p.charAt(j?-?1)?!=?'*')?{ ????????return?isMatch(s.charAt(i?-?1),?p.charAt(j?-?1))?&&? ???????????????isMatch(s,?i?-?1,?p,?j?-?1); ????} ?? ????return??isMatch(s,?i,?p,?j?-?2)?||?isMatch(s,?i?-?1,?p,?j)?&& ????????????isMatch(s.charAt(i?-?1),?p.charAt(j?-?2)); } boolean?isMatch(char?a,?char?b)?{ ????return?a?==?b?||?b?==?'.'; } ``` 1. 遞歸函數的輸入參數有四個，分別是字符串 s，當前字符串 s 的下標，字符串 p，以及字符串 p 的當前下標。由主函數可以看到，兩個字符串的下標都是從最后一位開始。 2. 若 p 字符串為空，并且如果 s 字符串也為空，就表示匹配。 3. 當 p 字符串不為空，而 s 字符串為空，如上例所示，當 s 為空字符串，而 p 等于 a*，此時只要 p 總是由 '*'組合構成，一定能滿足匹配，否則不行。 4. 若 p 的當前字符不是 '*'，判斷當前的兩個字符是否相等，如果相等，就遞歸地看前面的字符。 5. 否則，如果 p 的當前字符是 '*'： 用 '*' 組合表示空字符串，看看是否能匹配； 用 '*' 組合表示一個字符，看看能否匹配。 **動態規劃法** 遞歸的方法比較好理解，但是容易造成重疊計算。為了避免重疊計算，可以用動態規劃，自底向上地實現剛才的策略。 代碼實現 ``` //?分別用?m?和?n?表示?s?字符串和?p?字符串的長度 boolean?isMatch(String?s,?String?p)?{ ????int?m?=?s.length(),?n?=?p.length(); ????//?定義一個二維布爾矩陣?dp ????boolean[][]?dp?=?new?boolean[m?+?1][n?+?1]; ????//?當兩個字符串的長度都為?0，也就是空字符串的時候，它們互相匹配 ????dp[0][0]?=?true; ?? ????for?(int?j?=?1;?j?<=?n;?j++)?{ ????????dp[0][j]?=?j?>?1?&&?p.charAt(j?-?1)?==?'*'?&&?dp[0][j?-?2]; ????} ????for?(int?i?=?1;?i?<=?m;?i++)?{ ????????for?(int?j?=?1;?j?<=?n;?j++)?{ ????????????//?p?的當前字符不是?'*'，判斷當前的兩個字符是否相等，如果相等，就看?dp[i-1][j-1]?的值，因為它保存了前一個匹配的結果 ????????????if?(p.charAt(j?-?1)?!=?'*')?{ ????????????????dp[i][j]?=?dp[i?-?1][j?-?1]?&&? ???????????????????isMatch(s.charAt(i?-?1),?p.charAt(j?-?1)); ????????????}?else?{ ????????????????dp[i][j]?=?dp[i][j?-?2]?||?dp[i?-?1][j]?&&? ???????????????????isMatch(s.charAt(i?-?1),?p.charAt(j?-?2)); ????????????} ????????} ????} ?? ????return?dp[m][n]; } boolean?isMatch(char?a,?char?b)?{ ????return?a?==?b?||?b?==?'.'; ? } ``` 注意： * 初始化二維矩陣第一行的所有值時，當 s 字符串為空，對于 p 字符串的任何一個位置，要使到這個位置的子串能和空字符串匹配，要求該子串都是由一系列的 '*' 組合構成。 * 對二維矩陣填表，運用到的邏輯跟遞歸一摸一樣。 * p 的當前字符不是 '*'，判斷當前的兩個字符是否相等。如果相等，就看?dp[i-1][j-1]?的值，因為它保存了前一個匹配的結果。 * 如果 p 的當前字符是 '*'： * 用 '*' 組合表示空字符串，能否匹配，也就是?dp[i][j - 2]； * 用 '*' 組合表示一個字符，能否匹配，也就是?dp[i - 1][j]。 * [ ] 復雜度分析 運用動態規劃，把時間復雜度控制在 O(n2)，而空間復雜度也是 O(n2)。 建議：LeetCode 上有一道跟這題十分類似的題目，第 44 題，通配符匹配。分析例題的思路，所運用的策略，以及代碼的實現，都有很多非常相似的地方。大家一定要去做做看，舉一反三才能加深印象。