10. Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' 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

S1: recursion & backtracking

关键在于”x*“ 可以匹配“”空字符或者 ”xx..x“。递归穷举所有可能情况。

corner case: 单独星号开头不能匹配任何字符，"a"和"*a"不匹配

    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();
        if(p.size() > 1 && p[1] == '*')
            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)));
    }

S2: DP

match[i][j]: if s[0..i-1] matches p[0..j-1]

状态转移方程：

• 当前p[i-1]是*时，‘*’要么删除前置字符；要么重复前置字符 match[i][j] = match[i][j-2] || (match[i-1][j] && (s[i-1] == p[j-2]||p[j-2]=='.')

• 当前p[i-1]不是*时，match[i][j]=match[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.')

    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();
        int m = s.size();
        int n = p.size();
        vector<vector<bool>> match(m+1, vector<bool>(n+1, false));
        match[0][0] = true;
        for(int i = 2; i <= n; ++i){
            match[0][i] = match[0][i-2] && p[i-1] == '*';
        }
        for(int i = 1; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                //’*‘不会出现在p的第一位所以不用考虑j=1的情况
                if(p[j-1] == '*') match[i][j] = match[i][j-2] || (match[i-1][j] && (s[i-1] == p[j-2]||p[j-2]=='.'));
                else match[i][j] = match[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
            }
        }
        return match[m][n];
    }

44. Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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", "") → true
isMatch("aa", "a") → true
isMatch("ab", "?_") → true
isMatch("aab", "c_a*b") → false

S1:backtracking O(n) ?

1. 当”*“出现的时候存储当时s和p的index为s_pos和p_pos
2. 当出现不match且”*“出现过的情况时，开始backtraking。s回到s_pos+1(s_pos本身也要++), p回到星号后一位p_pos+1

注意要loop through s，最后根据j是否到p.size判断是否完全match

    bool isMatch(string s, string p) {
        int idx_s = 0, idx_p = 0, star_s = -1, star_p = -1;
        while (idx_s < s.size()) {
            if (s[idx_s] == p[idx_p] || p[idx_p] == '?') {
                idx_s++;
                idx_p++;
            } else if (p[idx_p] == '*') {
                star_s = idx_s;
                star_p = idx_p + 1;
                idx_p++;
            } else if (star_p != -1) {  //backtracking
                star_s++;  //注意这里每次要从s与astroid 对应的位置+1重新开始
                idx_s = star_s;
                idx_p = star_p;
            } else {
                return false;
            }
        }
        while (idx_p < p.size() && p[idx_p] == '*') {
            idx_p++;
        }
        return idx_p == p.size();
    }

S2: DP O(mmn)

dp[i][j]存储s 0~i - 1与p 0 ~ j - 1是否match。

    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            dp[0][i] = dp[0][i - 1] && p[i - 1] == '*';
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    for (int k = 0; k <= i; ++k) {
                        if (dp[k][j - 1]) {
                            dp[i][j] = true;
                            break;
                        }
                    }
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
                }
            }
        }
        return dp[m][n];
    }