# [C++] Clean Code - 7 Lines DP - match[i][j] = isMatch(s.substr(i), p.substr(j))

• DP Solution

``````/**
* if pattern runout - false
* if string runout - pattern == "" or pattern == "a*b*c*"
*
* Definitions:
*      match[i][j] = isMatch(s.substr(i), p.substr(j));
*      match[0][0] = isMatch(s, p);
*      match[m][n] = isMatch("", ""); // m = s.size(), n = p.size();
*
* Pattern:
* match[i][j] =
*               p[j+1] == '*' ? s[i] == p[j] && match[i+1][j]      // match("abc", "a*bc") if match("bc", "a*bc")
*                                            || match[i][j + 2];   // match("bc", "a*bc") if match("bc", "bc")
*               p[j] == '.' ? match[i+1][j+1]       // s[i] could be char, as long as match[i+1][j+1]
*               p[j] == '\w' ? s[i] == p[j] && match[i+1][j+1];    // match("labc", "la*bc") if match("abc", "a*bc")
* Expression:
*  match[i][j] = j + 1 < n && p[j + 1] == '*'          // next char of pattern is '*'
*      ? match[i][j + 2] || i < m && match[i + 1][j] && (p[j] == '.' || s[i] == p[j])
*      : i < m && match[i + 1][j + 1] && p[j] != '*' && (p[j] == '.' || s[i] == p[j]);
``````

Code

``````class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool>> match(m + 1, vector<bool>(n + 1, false));
match[m][n] = true;
for (int i = m; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)    // match[i != m][n] = false; no need to process
match[i][j] = j + 1 < n && p[j + 1] == '*' ? match[i][j + 2] || i < m && (p[j] == '.' || s[i] == p[j]) && match[i + 1][j] : i < m && (p[j] == '.' || s[i] == p[j]) && match[i + 1][j + 1];
return match[0][0];
}
};
``````

A partially iterated example

`````` * s = "abcd"
* p = "a.c*e*d"
*
*     0 1 2 3 4 5 6 7
*     a . c * e * d 0
* 0 a               0
* 1 b               0
* 2 c               0
* 3 d               0
* 4     0 0 0 0 0 0 1
*
*     0 1 2 3 4 5 6 7
*     a . c * e * d 0
* 0 a               0
* 1 b               0
* 2 c 0 1 1 0 0 0 0 0
* 3 d 0 0 1 0 1 0 1 0
* 4     0 0 0 0 0 0 1
*/
``````

Recursion

``````class Solution {
public:
bool isMatch(string s, string p) {
return match(s, p, 0, 0);
}

bool match(string s, string p, int s0, int p0) {
if (s0 == s.length() && p0 == p.length()) {
return true;
}
else if (s0 == s.length()) { // string runout, match only if pattern is like "a*b*c*d*"
if ((p.length() - p0) % 2 == 1) {
return false;
}

for (int pi = p0; pi < p.length(); pi++) {
// if any even digit is not word char, or if any odd digit is not '*', cannot match
if ((pi - p0) % 2 == 0 ? (p[pi] == '*') : (p[pi] != '*')) {
return false;
}
}
return true;
}
else if (p0 == p.length()) { // pattern runout, can not match;
return false;
}

if (p0 + 1 < p.length() && p[p0 + 1] == '*') {
for (int si = s0; si < s.length() && (s[si] == p[p0] || p[p0] == '.'); si++) {
if (match(s, p, si + 1, p0 + 2)) {
return true;
}
}
return match(s, p, s0, p0 + 2);
}
else if (p[p0] == '.') {
return match(s, p, s0 + 1, p0 + 1);
}
else {
return s[s0] == p[p0] && match(s, p, s0 + 1, p0 + 1);
}
}
};
``````

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