<p>Given an input string <code>s</code>&nbsp;and a pattern <code>p</code>, implement regular expression matching with support for <code>&#39;.&#39;</code> and <code>&#39;*&#39;</code> where:</p>

<ul>
	<li><code>&#39;.&#39;</code> Matches any single character.​​​​</li>
	<li><code>&#39;*&#39;</code> Matches zero or more of the preceding element.</li>
</ul>

<p>The matching should cover the <strong>entire</strong> input string (not partial).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;a&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> &quot;a&quot; does not match the entire string &quot;aa&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;a*&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> &#39;*&#39; means zero or more of the preceding element, &#39;a&#39;. Therefore, by repeating &#39;a&#39; once, it becomes &quot;aa&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ab&quot;, p = &quot;.*&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> &quot;.*&quot; means &quot;zero or more (*) of any character (.)&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length&nbsp;&lt;= 20</code></li>
	<li><code>1 &lt;= p.length&nbsp;&lt;= 20</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
	<li><code>p</code> contains only lowercase English letters, <code>&#39;.&#39;</code>, and&nbsp;<code>&#39;*&#39;</code>.</li>
	<li>It is guaranteed for each appearance of the character <code>&#39;*&#39;</code>, there will be a previous valid character to match.</li>
</ul>

class Solution {
public:
    
    bool match(int i, int j, string& s, string& p, vector<int>& f, vector<vector<int>>& dp) {
	if (dp[i][j] != -1) {
		return dp[i][j];
	} else if (i == s.size()) {
		int k = j;
		while (k<p.size()) {
			if (f[k] == -1) {
				k++;
			} else {
				break;
			}
		}
		dp[i][j] = (k == p.size());
	} else {
		dp[i][j] = 0;
		if (s[i] == p[j] || p[j] == '.') {
			if (f[j] == -1) {
				dp[i][j] = match(i+1, j, s, p, f, dp) || match(i, j+1, s, p, f, dp);
			} else {
				dp[i][j] = match(i+1, j+1, s, p, f, dp);
			}
		}
		if (!dp[i][j] && f[j] == -1) {
			dp[i][j] = match(i, j+1, s, p, f, dp);
		}
	}
	return dp[i][j];
}
    
    bool isMatch(string s, string p) {
        int m = s.size();
	vector< int > f;
	string p_red;
	for (char& c : p) {
		if (c == '*') {
			f.back() = -1;
		} else {
			f.push_back(1);
			p_red += c;
		}
	}
	int n = f.size();
	vector<vector<int>> dp(m+1, vector<int>(n+1, -1));
	dp[m][n] = 1;
	for (int i=m-1; i>=0; i--) {
		dp[i][n] = 0;
	}
	return match(0, 0, s, p_red, f, dp);
    }
};
8806