# My concise recursive and DP solutions with full explanation in C++

• Please refer to my blog post if you have any comment. Wildcard matching problem can be solved similarly.

``````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));
}
};

class Solution {
public:
bool isMatch(string s, string p) {
/**
* f[i][j]: if s[0..i-1] matches p[0..j-1]
* if p[j - 1] != '*'
*      f[i][j] = f[i - 1][j - 1] && s[i - 1] == p[j - 1]
* if p[j - 1] == '*', denote p[j - 2] with x
*      f[i][j] is true iff any of the following is true
*      1) "x*" repeats 0 time and matches empty: f[i][j - 2]
*      2) "x*" repeats >= 1 times and matches "x*x": s[i - 1] == x && f[i - 1][j]
* '.' matches any single character
*/
int m = s.size(), n = p.size();
vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));

f[0][0] = true;
for (int i = 1; i <= m; i++)
f[i][0] = false;
// p[0.., j - 3, j - 2, j - 1] matches empty iff p[j - 1] is '*' and p[0..j - 3] matches empty
for (int j = 1; j <= n; j++)
f[0][j] = j > 1 && '*' == p[j - 1] && f[0][j - 2];

for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (p[j - 1] != '*')
f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || '.' == p[j - 1]);
else
// p[0] cannot be '*' so no need to check "j > 1" here
f[i][j] = f[i][j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];

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

• your dynamic programming solution is perfect.

• this is the best answer i have seen under this problem!

• This post is deleted!

• I had difficulty understanding other answers, so I came up with an easy-to-understand one.

• DP may be the proper way. My recursive solution in python always goes overtime.

• Seconded. Recursion is mainly for showing the basic idea.

• Great solution! Just one comment: I feel " 2) "x*" repeats 1 time and matches x: b[i + 1][j]" is not necessary since condition (3) includes it already:

• @xinxiang You are right, nice catch. It is inconsistent with the recursive version. I updated both versions. Please let me know if there is any other issue.

• How could you ensure the 'p[1]' and 'p.substr(2)' is exist ,but not overflow？

• (A) p[1]: If pos is equal to the string length, the function returns a reference to the null character http://www.cplusplus.com/reference/string/string/operator[]/. (B)
p.substr(2): only called when p[1] is '*', so p's length is at least 2 and substr(2) is good http://www.cplusplus.com/reference/string/string/substr/.

• This post is deleted!

• Java equivalent

``````public boolean isMatch(String s, String p) {
/*
'match' below including .
f(i,j) means s where s.len=i matches p where p.len=j
f(i,j) =
if (p_j-1 != * ) f(i-1, j-1) and s_i-1 matches p_j-1
if (p_j-1 == * )
* matches zero times: f(i,j-2)
or * matches at least one time: f(i-1,j) and s_i-1 matches p_j-2
*/

if (!p.isEmpty() && p.charAt(0) == '*') {
return false;   // invalid p
}

boolean[][] f = new boolean[s.length() + 1][p.length() + 1];

// initialize f(0,0)
f[0][0] = true;

// f(k,0) and f(0,2k-1) where k>=1 are false by default

// initialize f(0,2k) where p_2k-1 = * for any k>=1
for (int j = 1; j < p.length(); j+=2) {
if (p.charAt(j) == '*') {
f[0][j+1] = f[0][j-1];
}
}

for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) != '*') {
f[i][j] = f[i - 1][j - 1] && isCharMatch(s.charAt(i - 1), p.charAt(j - 1));
} else {
f[i][j] = f[i][j - 2] || f[i - 1][j] && isCharMatch(s.charAt(i - 1), p.charAt(j - 2));
}
}
}

return f[s.length()][p.length()];
}

// no * in p
private boolean isCharMatch(char s, char p) {
return p == '.' || s == p;
}``````

• What is the run time of your recursive solution ? If you please mention.

• Nice code!
Can you explain why we must initialize f(0,2k) where p_2k-1 = * ? I know it is necessary but I don't understand why.

• f(i, j) depends on f(i-1, j) or f(i, j-1) which means that i will hit zero while j is still greater than 0. In this case f(0, someJ) cannot be evaluated recursively because i cannot be reduced further more i.e. f(-1, someJ) is not valid

• Hi, how do you know p[0] cannot be * ?

• if p[0] = '*', the string must be an invalid string.
that is what Regular Expression defined.

• This post is deleted!

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