# Concise and easy to understand C++ iterative dp solution with explanations.

• The state dp[i][j] denote whether s[0:i) and p[0:j) match.
We then have 5 equations:

1. When regex p is empty, it matches no string, except an empty one.
2. 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*"
3. 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];
4. 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.
5. 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];
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.