乘風破浪：LeetCode真題_010_Regular Expression Matching
一、前言
? ? 關于正則表達式我們使用得非常多，但是如果讓我們自己寫一個，卻是有非常大的困難的，我們可能想到狀態機，確定，非確定狀態機確實是一種解決方法，不過需要消耗很大的時間去推理和計算，對于正則表達式的縮小版，我們往往可以通過遞歸，遞推，動態規劃等方法來解決。
二、Regular Expression Matching
2.1 問題理解
2.2 問題分析和解決
??? 遇到這樣的問題，我們想到了遞歸，對于.是很好處理和匹配的，但是如果和*結合起來就變化無窮了，正是因為*我們才要遞歸。
??? 讓我們看看官方的答案：
class Solution {public boolean isMatch(String text, String pattern) {if (pattern.isEmpty()) return text.isEmpty();boolean first_match = (!text.isEmpty() &&(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));if (pattern.length() >= 2 && pattern.charAt(1) == '*'){return (isMatch(text, pattern.substring(2)) ||(first_match && isMatch(text.substring(1), pattern)));} else {return first_match && isMatch(text.substring(1), pattern.substring(1));}}
}
??? 如果模式串和源串第一個字符能夠正常匹配，并且不為空，模式串的第二個字符不為'*'，那么我們可以繼續遞歸匹配下面的東西：
1 return first_match && isMatch(text.substring(1), pattern.substring(1));
??? 如果模式串的長度大于1，并且第二個字符是*,那么我們就有可能匹配到源串的很多的字符，也就相當于將源串已經匹配的去掉，拿剩下的和整個模式串繼續比較，此時*發揮了作用，或者比較源串與去掉了*的模式串，因為*沒有能夠發揮作用。于是就得到了：
1 if (pattern.length() >= 2 && pattern.charAt(1) == '*'){ 2 return (isMatch(text, pattern.substring(2)) || 3 (first_match && isMatch(text.substring(1), pattern))); 4 }
???? 除此之外我們還可以使用動態規劃算法：
class Solution {public boolean isMatch(String text, String pattern) {boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];dp[text.length()][pattern.length()] = true;for (int i = text.length(); i >= 0; i--){for (int j = pattern.length() - 1; j >= 0; j--){boolean first_match = (i < text.length() &&(pattern.charAt(j) == text.charAt(i) ||pattern.charAt(j) == '.'));if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];} else {dp[i][j] = first_match && dp[i+1][j+1];}}}return dp[0][0];}
}
???? 首先我們定義dp[i][j]代表源串T[i:]和模式串P[j:]是匹配的，其中i,j為源串和模式串的下標，于是我們只要求得dp[0][0]的值就可以了。我們已知的條件是：
dp[text.length()][pattern.length()] = true; ???? 于是我們從后往前倒求最終的dp[0][0]，通過如下的判斷，看看是哪一種情況，然后根據相應的情況采取不同的遞推策略，最終得到結果：
1 boolean first_match = (i < text.length() && 2 (pattern.charAt(j) == text.charAt(i) || 3 pattern.charAt(j) == '.')); 4 if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){ 5 dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j]; 6 } else { 7 dp[i][j] = first_match && dp[i+1][j+1]; 8 }
?????? 同樣的我們算法也是使用了遞歸和動態規劃：
??? 在動態規劃方面我們使用match[i]來表示對于源串從i到最后（T[i:]）都是能夠匹配的，于是之用求match[0]即可。
import java.util.Arrays;public class Solution {/*** Implement regular expression matching with support for '.' and '*'.* '.' Matches any single character.* '*' Matches zero or more of the preceding element.** 題目大意：* 實現一個正則表達式匹配算法，.匹配任意一個字符，*匹配0個或者多個前導字符*/public boolean isMatch(String s, String p) {boolean[] match = new boolean[s.length() + 1]; Arrays.fill(match, false);match[s.length()] = true;//剛開始滿足需要for (int i = p.length() - 1; i >= 0; i--) {if (p.charAt(i) == '*') {for (int j = s.length() - 1; j >= 0; j--) {
//原來就是false只有能夠為真，才為真。match[j] = match[j] || match[j + 1]&& (p.charAt(i - 1) == '.' || s.charAt(j) == p.charAt(i - 1));}i--;} else {for (int j = 0; j < s.length(); j++) {
//從前往后，只有到了已經有true的時候才能生效。如果從后往前反而有問題。 match[j] = match[j + 1]&& (p.charAt(i) == '.' || p.charAt(i) == s.charAt(j));}//將最后的置為假，本來就應該不真，便于以后的判斷match[s.length()] = false;}}return match[0];}// 下面的代碼用時比較長public boolean isMatch2(String s, String p) {// 輸入都為nullif (s == null && p == null) {return true;}// 有一個為nullelse if (s == null || p == null) {return false;}return isMatch(s, 0, p, 0);}/*** 正則表達式匹配** @param s 匹配串* @param sIdx 當前匹配的位置* @param p 模式串* @param pIdx 模式串的匹配位置* @return 匹配結果*/public boolean isMatch(String s, int sIdx, String p, int pIdx) {// 同時到各自的末尾if (s.length() == sIdx && p.length() == pIdx) {return true;}// 當匹配串沒有到達末尾，模式串已經到了末尾else if (s.length() != sIdx && p.length() == pIdx) {return false;}// 其它情況else {// 如果當前匹配的下一個字符是*號if (pIdx < p.length() - 1 && p.charAt(pIdx + 1) == '*') {// 匹配串未結束并且當前字符匹配（字符相等或者是.號）if (sIdx < s.length() && (s.charAt(sIdx) == p.charAt(pIdx) || p.charAt(pIdx) == '.')) {return isMatch(s, sIdx + 1, p, pIdx + 2) // 匹配串向前移動一個字符（只匹配一次）|| isMatch(s, sIdx + 1, p, pIdx) // 匹配串向前移動一個字符（下一次匹配同樣的（模式串不動））|| isMatch(s, sIdx, p, pIdx + 2); // 忽略匹配的模式串} else {// 忽略*return isMatch(s, sIdx, p, pIdx + 2);}}// 匹配一個字符if (sIdx < s.length() && (s.charAt(sIdx) == p.charAt(pIdx) || p.charAt(pIdx) == '.')) {return isMatch(s, sIdx + 1, p, pIdx + 1);}}return false;}}
?
??? 如下表所示，使用遞歸需要1163ms而使用動態規劃需要20ms，差別非常顯著。
三、總結
???? 對于一些比較困難的問題，我們需要從不同的角度考慮，解決問題的方法可以從遞歸，遞推，動態規劃等方面去考慮。
