# 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
```

Thoughts:

1. similar to [44. Wildcard Matching](https://code.taozirui.com/lc/string/wildcard-matching)
2. Recursion:
   1. if there is a X\* in pattern string: can match empty string ( so we jump to matching the rest) or matching current string ( so we compare them one by one)
   2. if current pattern string is NOT a character followed by a \* wildcard, just check whether the current char matches the one in the input string. 
3. DP idea: f\[i]\[j]: if s\[0..i-1] matches p\[0..j-1] 1. if p\[j - 1] != '\*'
   1. f\[i]\[j] = f\[i - 1]\[j - 1] && s\[i - 1] == p\[j - 1]
   2. if p\[j - 1] == '\*', denote p\[j - 2] with x
      1. 1\) "x\*" repeats 0 time and matches empty: f\[i]\[j - 2]
      2. 2\) "x\*" repeats >= 1 times and matches "x\*x": s\[i - 1] == x && f\[i - 1]\[j]

**Code T: O(n) S: O(n^2)**

```cpp
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty())    return s.empty();

        if ('*' == p[1])
            // x* matches empty string or at least one character: x* -> xx*
            // *s is to ensure s is non-empty
            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));
    }
};
```

**Code DP T: O(n^2)**

```cpp
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> f (m + 1, vector<bool>(n + 1, false));
        f[0][0] = true;
        for (int j = 1;  j <= n; j++){
            f[0][j] = j > 1 && f[0][j-2] && '*' == p[j - 1];
        }

        for( int i = 1; i <= m ; i++){
            for(int j = 1; j <= n; j++){
                if(p [j-1] == '*' && j > 1)
                    f[i][j] = (f[i][j - 2])||(s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];
                else
                    f[i][j] = (s[i - 1] == p[j - 1] || '.' == p[j-1]) && f[i - 1][j - 1];
            }
        }

        return f[m][n];
    }
};
```

Special Thanks [Pale Blue Dot's](http://xiaohuiliucuriosity.blogspot.com/2014/12/regular-expression-matching.html) solution