10.Regular Expression Matching

來自專欄 LeetCode打怪-升級-通關

10. Regular Expression Matching

#1 動態規劃[AC]

在正則表達式中，由於不同的字元會有不同的匹配規則，其中.和*比較特別，需要對這兩類字元進行分類討論。

• 定義狀態dp[i][j]表示輸入串長度為i，模式串長度為j時，是否能匹配。
• 初始化狀態值：
• 輸入串為空，模式串為空： dp[0][0]必然可以匹配，即dp[0][0]=true
• 輸入串非空，模式串為空：由於模式串為空，此時必然不可匹配，即dp[i][0]=false,i>0
• 輸入串為空，模式串非空：此時如果模式串中有*，則是可以匹配0個前面的字元的，所有我們通過條件p.charAt(j-1) == * && dp[0][j-2]來判斷是否可匹配
• 轉移方程，轉移方程表示通過已知的狀態值來求解未知的狀態值，在這裡就是我們要求解dp[i][j]，但是對於所有長度小於i的輸入串和長度小於j的模式串，我們已知其匹配情況。現在，我們怎麼利用前面的信息，來得到dp[i][j]的值。我們首先需要分析模式串的當前字元來做判斷:
• p.charAt(j-1) == s.charAt(i-1)當前模式串字元一樣，可以將當前字元匹配掉，然後狀態轉化如下:dp[i][j] = dp[i-1][j-1];
• p.charAt(j-1) == .當前模式串字元為.，可以匹配任意的字元，可以將當前輸入串字元匹配掉，然後狀態轉化為:dp[i][j] = dp[i-1][j-1]
• p.charAt(j-1) == *由於*可以匹配0個或多個它的上一個字元，所以根據上一個字元的不同還需要做不同的分析：
• p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != .，這種情況說明上一個字元即不是.，也不和輸入串的當前字元一樣，所有無法用一個或多個上一個字元對輸入串進行匹配，此時*只能匹配0個上一個字元:dp[i][j] = dp[i][j-2];
• 如果是這個條件里，說明上一個字元和輸入串的當前字元是可以進行匹配的，故此時*即可以匹配0個前一個字元，也可以匹配1個前一個字元，也可以匹配多個前一個字元:dp[i][j] = (dp[i][j-1] || dp[i-1][j] || dp[i][j-2])

整個題目的難點在於發現該題目能夠用動態規劃的方式進行求解，並且在求解轉移方程的時候，根據模式串當前字元的不同，進行不同的分類討論。

class Solution { public boolean isMatch(String s, String p) { if(s == null || p == null) return false; //定義狀態 boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]; //初始狀態賦值 dp[0][0] = true; for(int i=1; i<=s.length(); i++) dp[i][0] = false; for(int j=1; j<=p.length(); j++) if(p.charAt(j-1) == * && dp[0][j-2]) dp[0][j] = true; //利用初始狀態值 以及 轉移方程 求解未知狀態值， 直到最終狀態 for(int i=1; i<=s.length(); i++){ for(int j=1; j<=p.length(); j++){ //case 1 if(p.charAt(j-1) == s.charAt(i-1)) dp[i][j] = dp[i-1][j-1]; else if(p.charAt(j-1) == .) dp[i][j] = dp[i-1][j-1]; else if(p.charAt(j-1) == *){ if(p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != .) dp[i][j] = dp[i][j-2]; else dp[i][j] = (dp[i][j-1] || dp[i-1][j] || dp[i][j-2]); }else dp[i][j] = false; } } return dp[s.length()][p.length()]; }}

推薦閱讀：