runtime 0 ms, beats 100% of cpp submissions
O(mn) solution with explanation

tags: regex, dp

Regular Expression Matching

📖 description

給定字串 s 與 p ，其中 s 表示需要被 match 的字串， p 表示用來 match 的字串，回傳 s 是否可以被 p match

規則 : 
    . 表示 match 一個任意字元
    * 表示 match 零或多個前面的字元

ex. 
    "aa" 不可被 "a"  match
    "aa" 可被   "a*" match
    "ab" 可被   ".*" match

🧠 solution

在優化整體架構之前，要先想一個解決問題的基礎

首先，怎麼樣確定當前字元有沒有 match ，有兩種狀態 ( i,j 代表當前要處理的的字元)

  • s[i] == p[j]
  • p[j] == ‘.’
以及如何處理 * 的狀態 ( m,n 表示字串長度)
- 如果當前的 * 代表 0 次，則我們要跳過 * 的部分，檢查 s[i~m] 與 p[j+2~n] 是否 match 
- 如果當前的 * 代表 1 或多次，則我們不移動 p 的 index ，繼續往後看 s[i+1~m] 與 p[j~n] 是否 match

dp

在有了基礎架構後，我們可以使用一個陣列來儲存每個狀態的 match 結果，來加速

狀態表示如下
dp[i][j] 表示 s[1~i] 與 p[1~j] 是否 match

⏳ time complexity

需要遍歷兩個字串，使用 dp 後不用重新查看更多的狀態，時間複雜度為 O(mn)
總時間複雜度 O(mn)

📝 code

base structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isMatch(string s, string p) {
        return re(s,p,0,0);
    }
    bool re(string& s, string& p,int i, int j){
        bool match = false;
        if(j==p.size()){
            return i==s.size(); // 如果兩邊都找完了，表示 match 成功
        }
        if(i<s.size() && (s[i]==p[j] || p[j]=='.')){            // 當前的符號有沒有被 match 
            match = true;
        }
        if(j+1<p.size() && p[j+1]=='*'){                        // 如果遇到 * ，考慮0次或多次的兩種狀態
            return (re(s,p,i,j+2) || (match && re(s,p,i+1,j))); // 如果0次，不用管當前的 match 情形
        }
        return (match && re(s,p,i+1,j+1));                      // 正常的移動
    }
};

dp optimization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<int>> dp(21,vector<int>(31,-1));  // 內容初始化
        return re(dp,s,p,0,0);
    }
    bool re(vector<vector<int>>& dp, string& s, string& p,int i, int j){
        if(dp[i][j]!=-1){ // 如果當前狀態出現過就回傳
            return dp[i][j];
        }
        bool match = false;
        if(j==p.size()){
            return dp[i][j] = (i==s.size());
        }
        if(i<s.size() && (s[i]==p[j] || p[j]=='.')){
            match = true;
        }
        if(j+1<p.size() && p[j+1]=='*'){
            return dp[i][j] = (re(dp,s,p,i,j+2) || (match && re(dp,s,p,i+1,j)));
        }
        return dp[i][j] = (match && re(dp,s,p,i+1,j+1));
    }
};