LeetCode 10. Regular Expression Matching [Hard] [C++] 解題筆記

這題給定一個 string (s) 與一個 pattern (p) ，要求我們實作支援 ' . ' 與 ' * ' 操作的正規表示法。

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

The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
	
p could be empty and contains only lowercase letters a-z, and characters like . or *.

EX:
    Input:
    s = "aa"
    p = "a"
    Output: false
    Explanation: "a" does not match the entire string "aa".
    Input:
    s = "aa"
    p = "a*"
    Output: true
    Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
    Input:
    s = "ab"
    p = ".*"
    Output: true
    Explanation: ".*" means "zero or more (*) of any character (.)".
    Input:
    s = "aab"
    p = "c*a*b"
    Output: true
    Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
    Input:
    s = "mississippi"
    p = "mis*is*p*."
    Output: false
想法:
    這題除了直接呼叫 C++11 的 regex engine 之外，可以使用 recursive 或是 DP 的方式來求解，首先 recursive 的方式
若當前字元為 '*' 則前面一定要有其他字元，因為以'*'為 string 開頭的話是未定義的行為，而'*'可以表示前一個字元重複 0 或 多次，
因此當 p 長度大於 1 且當前字元為 '*' 時，可以分成兩種情況進行搜索，第一，若'*'代表前一個字元重複 0 次則我們從 p 的下一個字元開始
去與 s 做 match，若'*'代表前一個字元重複多次則表示前一個字元必須與 s 的同位置的字元是match的，則 p 的前一個字元只能等於 s的同位置的字元
或是為 '.'(因為'.'可以表示任意字元) 然後我們再從 s 的下一個位置繼續與 p 做 match (因為 p 當前位置是'*'還能繼續 match)，第二種情況是，
p 的當前字元不是'*'，則 s 與 p 要 match 的話表示前一個字元必定相同，然後我們從 s 的下一個位置與 p 的下一個位置繼續做 match。
另外 DP 的方式概念也類似，我們可以用 dp[i][j] 代表 s 在長度 i 時s[0:i-1]是否與 p 在長度 j 時p[0:j-1]可以匹配，
則初始條件為 dp[0][0] = true，當兩者皆為空時可以匹配，而當 s 為空時，若當前位置 j 的 p 為 '*' 則是否匹配取決於 dp[0][j-2]，因為'*'可以
與前一個字元合併為空(repeated 0 times)，因此dp[0][j] = (p[j-1] == '*' && dp[0][j-2])，而當 s 不為空時，首先若是當前位置可以互相匹配即 
s[i - 1] == p[j - 1] || p[j - 1] == '.' ，則是否匹配取決於 dp[i - 1][j - 1]，若當前位置互相不匹配時則只有 p[j - 1] == '*'時才有機會匹配，而 p[j - 1] == '*' 時，
又可以分為 p[j - 2] 與 s[i - 1] 不匹配與 p[j - 2] 與 s[i - 1] 匹配兩種情況，若 p[j - 2] 與 s[i - 1] 不匹配則 p[j - 1] 只能解讀成p[j - 2]匹配 0 次能有機會 match
，因此 dp[i][j] = dp[i][j-2]，若 p[j - 2] 與 s[i - 1] 匹配則可以將 '*' 解讀成 p[j - 2] 匹配 0 次 , 匹配 1 次 或 匹配多次，
因此 dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];，完整 dp 狀態轉移式如下:

dp[0][0] = true;
dp[0][j] = true , if p[j - 1] == '*' && dp[0][j - 2] = true
dp[i][j] = dp[i][j - 2] , if s[j - 1] != p[j - 2] || p[j - 2] != '.'
            = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j], if s[j - 1] == p[j - 2] || p[j - 2] == '.'
 
完整程式碼:
解法一(regex engine, C++11):
class Solution {
public:
    bool isMatch(string s, string p) {
        regex pattern(p);
        return regex_match(s, pattern);
    }
};
解法二:(recursive):
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) { return s.empty(); }
        // since '*' without preceding element is not defined
        if (p.size() > 1 && p[1] == '*') {
            // treat '*' as repeat 0 or treat '*' as repeat 1 or multiple
            return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
        }
        else {
            return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));   
        }
        
        return false;
    }
};
解法三(DP):
class Solution {
public:
    bool isMatch(string s, string p) {
        // dp[i][j] = string s with len i matches string p with len j
        // this case is not defined, no preceding element before '*' is not defined
        // s = "a"
        // p = "*"
        vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
        dp[0][0] = true;
        // definitely not match when i = 1
        for (int i = 2; i <= p.size(); i++) {
            if (p[i - 1] == '*' && dp[0][i - 2]) {
                dp[0][i] = true;
            }
        }
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= p.size(); j++) {
                // if current char is match
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (j > 1) {
                    if (p[j - 1] == '*') {  
                    // if current char of p is '*'
                    // then we can treat * as represent 0 times of preceding, so if the first two char of p is match to s[i] then we can match
                    // i.e. s = abc, p = ac*, we treat c* as null
                        if (p[j - 2] != s[i - 1] && p[j - 2] != '.') {
                            dp[i][j] = dp[i][j - 2];
                        }
                        else {
                            // treat * as repeat 0 or 1 or multiple
                            // dp[i - 1][j], ex: s = "aaaaa", p = "a*", i = 3, s[0:i-1] = "aaa", j = 2, p[0:j-1] = "a*"
                            // 'a' can repeat multiple times to match s[0:i-1], so dp[i][j] is up to dp[i - 1][j], i.e. 前面是否能用 '*'  match
                            dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                        }
                    }
                }
            }
        }
        
        return dp[s.size()][p.size()];
    }
};