The state **dp[i][j]** denote whether **s[0:i)** and **p[0:j)** match.

We then have 5 equations:

- When regex
**p**is empty, it matches no string, except an empty one. - When string
**s**is empty, it matches regex that has the repetitive pattern which has pairs of any character other than * and followed by a*, e.g. "a** b*" or ".* x* z*" - If current char in
**s**and**p**matches, or current char in**p**is a ".",**dp[i][j]**reduces to subproblem**dp[i-1][j-1];** - If current char in the
**p**is *, and the char before it matches the current char in**s**or is a ".",**dp[i][j]**is true if**dp[i-1][j-1]**just like in 3, or**dp[i-1][j]**is true, this accounts for a * matching multiple repeated characters. - Finally, on top of above formulas, if current char in
**p**is a *,**dp[i][j]**is true if any of**dp[i][j-1]**or**dp[i][j-2]**is true. This accounts for the fact that * expressions in the regex can be skipped safely.

Feel free to suggest improvement or ask a question. :)

class Solution {

public:

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

};