正則表達式匹配dp

Question

我想了解着名的正則表達式匹配DP算法之一。爲了以防萬一，人們不知道這裏是描述和算法。

'.' Matches any single character. 
'*' Matches zero or more of the preceding element. 

The matching should cover the entire input string (not partial). 

The function prototype should be: 
bool isMatch(const char *s, const char *p) 

---

Some examples: 
isMatch("aa","a") → false 
isMatch("aa","aa") → true 
isMatch("aaa","aa") → false 
isMatch("aa", "a*") → true 
isMatch("aa", ".*") → true 
isMatch("ab", ".*") → true 
isMatch("aab", "c*a*b") → true 


static boolean isMatch(String s, String p) { 
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]; 
    dp[0][0] = true; 
    for (int i = 1; i < dp[0].length; i++) { 
     if (p.charAt(i - 1) == '*') { 
      dp[0][i] = dp[0][i - 2]; 
     } 
    } 
    for (int i = 1; i < dp.length; i++) { 
     for (int j = 1; j < dp[0].length; j++) { 
      char schar = s.charAt(i - 1); 
      char pchar = p.charAt(j - 1); 
      if (schar == pchar || pchar == '.') { 
       dp[i][j] = dp[i - 1][j - 1]; 
      } else if (pchar == '*') { 
       if (schar != p.charAt(j - 2) && p.charAt(j - 2) != '.') { 
        // - a b * 
        // - t f f f 
        // a f t f t // b != a and b != '.' thus treat b* as 0 match 
        dp[i][j] = dp[i][j - 2]; 
       } else { 
        // - a b * 
        // - t f f f 
        // a f t f t 
        // b f f t t // dp[i][j - 2] 0 match or dp[i][j - 1] 1 math or dp[i - 1][j] 2+ match (not sure why) 
        dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j]; 
       } 
      } 
     } 
    } 
    return dp[s.length()][p.length()]; 
} 

我瞭解最的一部分，但這一部分，我不明白這一點

dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j]; 

dp[i - 1][j]人說，這將覆蓋2+的比賽，但不明白這一點部分。有人可以解釋爲什麼我需要檢查dp[i - 1][j]？

Answer 1

假設字符串不包含特殊字符'。 '和'*'因爲否則代碼呈現將無法正常工作！

dp[i][j]代表什麼？

它表示，如果只有第一我字符串的字符和Ĵ模式的字符都認爲，他們不匹配？萬一

狀態過渡，我們在圖案遇到 '*'：

案例1：只取0號前面的'*'圖案的性格。

單獨的'*'並不意味着什麼。它依賴於它的前面的字符。

dp[i][j-2]會完全忽略在圖案前面的字符，因爲它僅考慮第一J-2字符，所以與前述沿着字符「*」在圖案（第j字符）被忽略。現在

---

如果它是在第i個字符在字符串和字符之前「*」碰巧是相同或字符之前的情況下「*」在圖案爲「。 '然後再增加1個案例。

觀察這裏：*可以匹配任何字符串

---

如果滿足上述條件，再考慮下面的情況。

情況2：前述字符的使用繼續 '*'用於一個或更多次。

dp[i-1][j]表示這一點。記住jth模式中的字符是'*'。

因此，如果第一I-1字符串匹配與圖案的第一Ĵ字符的其中第j字符是「*」（這表明我們已經使用字符之前「*」至少一次），那麼我們可以說，在字符串匹配，首先我字符與第一Ĵ模式字符作爲我們已經確保了第i個字符前面的字符匹配「*」模式。

殼體dp[i][j-1]是多餘的，在殼體覆蓋2.

注意：前述字符解釋爲dp[i][j-1]

dp[i][j-1]匹配冗餘僅一次 '*'。它已被覆蓋在dp[i-1][j]。

原因：

我們知道第i個字符匹配第j-1字符（請記住，我們考慮到這種情況下前檢查）。

所以dp[i][j-1] = dp[i-1][j-2]這已經在計算dp[i-1][j]計算。

dp[i-1][j]更強大，因爲dp[i-1][j] = dp[i-1][j-2] || dp[i-2][j]作爲第j個字符是'*'。所以這就是賦予我們不止一次使用角色的記憶屬性。

Answer 2

我會用一些更加非正式的表示法，讓我忍受。 首都將表示字符串（在可能包含特殊字符的模式中）和小寫字母'。'。 '*'將代表自己。我們假設我們將Ax與Bx進行匹配，即一些以A開頭的字符串（它本身就是一個字符串，如xyzz）以'x'結尾，模式以B開始（這本身就是一個模式，例如，x。*）以'x'結尾。結果與匹配A到B的結果相同（因爲我們別無選擇，只能將x與x匹配）。

我們可以編寫如下：

isMatch(Ax, Bx) = isMatch(A, B)

同樣，匹配斧通過是不可能的。

isMatch(Ax, Bx) = false

夠簡單。所以這將對應於兩個嵌套循環中的第一個if語句。

現在我們來看一個星號的情況。 匹配斧由*只能通過忽略Y *來完成（以零Y的），這是斧匹配B.

isMatch(Ax, By*) = isMatch(Ax, B)

然而，如果y由點或X，有取代是選擇。 我們將以Ax和Bx *爲例。這兩個選項都匹配斧B（意味着採取零X的）或匹配到Bx的*（手段獲取X-，但我們仍然可以採取更多這樣的格局不改）：

isMatch(Ax, Bx*) = isMatch(Ax, B) || isMatch(A, Bx*)

最後一會，在你的代碼，翻譯成：

dp[i][j] = dp[i][j - 2] || dp[i - 1][j]

所以現在我想知道如果你的問題是真正關心dp[i][j - 1]，因爲這就是會混淆我。

我可能是錯的，但似乎沒有必要。

它的含義是放下星號，即將「零或多個」 更改爲「正好一個」，其他兩種情況已經涵蓋，其中第一個跟隨第二個。