#LeetCode:10. Regular Expression Matching

最簡單的方式就是用 Backtracking 法(遞迴暴力法)一個一個去對,對錯了就回頭。但本題還可以優化成 DP 去解,與 LCS 或是 Edit Distance 的字串比對 DP 表公式有點類似,每一格 dp[i][j] 的意思是 s[1...i]p[1...j] 的比對結果, ij 為 0 時表示為該字串是空字串的時候,接著 DP 的公式含義如下:

  1. ij 都為 0 ,兩邊都是空字串自然是個完美比對,故為 true
  2. j = 0i > 0 ,則表示正規表達式是空字串,而該比對的字串有字,比對不成功,故皆為 false
  3. i = 0j > 0 ,則若正規表達式的前端皆為某個東西接 * 的話,則在為 * 的那時比對會是 true ,若中間出現了一個不是 * 的 pattern ,則就無法與空字串比對為成功,從那之後不管正規表達式裡有什麼就皆為 false
  4. i > 0j > 0 ,需分成兩種狀況:
    1. s[i] == p[j] || p[j] == '.' ,則表示兩字比對成功,則結果就取決於將兩邊比對成功的這組拿掉後的結果,故 dp[i][j] = dp[i-1][j-1]
    2. p[j] == '*',則有兩種可以的方式比對,將兩種方式的結果 OR 起來即是 dp[i][j] 的結果。
      1. * 可以為 0 ,則表示結果可以取決於這組 * 不在的狀況,也就是 dp[i][j-2]
      2. 若這組所選的字剛好可以跟 s[i] 比對,也就是 s[i] == p[j-1] || p[j-1] == '.' ,則結果也可以取決於將 s[i] 吃掉後的結果,也就是 dp[i-1][j]

這樣求到最後 dp[s.length()][p.length()] 即是答案。

C++(8ms)

/*******************************************************/
/* LeetCode 10. Regular Expression Matching            */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/09/30                                 */
/*******************************************************/
#include <vector>

class Solution {
public:
  bool isMatch(string s, string p) {
    vector<vector<bool>> dp(s.length() + 1, vector<bool>(p.length() + 1, false));

    /* Empty String */
    dp[0][0] = true;

    /* "" v.s. X*X*X*..... */
    for(int i = 2 ; i <= p.length() && p[i-1] == '*' ; i += 2){
      dp[0][i] = true;
    }

    /* s[0...i-1] v.s. p[0...j-1] */
    for(int i = 1 ; i <= s.length() ; ++i){
      for(int j = 1 ; j <= p.length() ; ++j ){
        int sIndex = i-1;
        int pIndex = j-1;

        if(p[pIndex] == '.' || s[sIndex] == p[pIndex]){
          dp[i][j] = dp[i-1][j-1];
        }
        else if(p[pIndex] == '*'){
          dp[i][j] = dp[i][j-2] || ((s[sIndex] == p[pIndex-1] || p[pIndex-1] == '.') && dp[i-1][j]);
        }
      }
    }

    return dp[s.length()][p.length()];
  }
};
廣告

Comment

There is no comment on this post. Be the first one.

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: