# Java 4ms dp solution with O(n^2) time and O(n) space beats 95%

• The dp algorithm is known by many other solutions. An optimization is to reduce the storage to O(n) with only one row of data.

``````public boolean isMatch(String s, String p) {
/**
* This solution is assuming s has no regular expressions.
*
* dp: res[i][j]=is s[0,...,i-1] matched with p[0,...,j-1];
*
* If p[j-1]!='*', res[i][j] = res[i-1][j-1] &&
* (s[i-1]==p[j-1]||p[j-1]=='.'). Otherwise, res[i][j] is true if
* res[i][j-1] or res[i][j-2] or
* res[i-1][j]&&(s[i-1]==p[j-2]||p[j-2]=='.'), and notice the third
* 'or' case includes the first 'or'.
*
*
* Boundaries: res[0][0]=true;//s=p="". res[i][0]=false, i>0.
* res[0][j]=is p[0,...,j-1] empty, j>0, and so res[0][1]=false,
* res[0][j]=p[j-1]=='*'&&res[0][j-2].
*
* O(n) space is enough to store a row of res.
*/

int m = s.length(), n = p.length();
boolean[] res = new boolean[n + 1];
res[0] = true;

int i, j;
for (j = 2; j <= n; j++)
res[j] = res[j - 2] && p.charAt(j - 1) == '*';

char pc, sc, tc;
boolean pre, cur; // pre=res[i - 1][j - 1], cur=res[i-1][j]

for (i = 1; i <= m; i++) {
pre = res[0];
res[0] = false;
sc = s.charAt(i - 1);

for (j = 1; j <= n; j++) {
cur = res[j];
pc = p.charAt(j - 1);
if (pc != '*')
res[j] = pre && (sc == pc || pc == '.');
else {
// pc == '*' then it has a preceding char, i.e. j>1
tc = p.charAt(j - 2);
res[j] = res[j - 2] || (res[j] && (sc == tc || tc == '.'));
}
pre = cur;
}
}

return res[n];
}``````

• Very very very smart solution.

• But this cannot match "a." "ab" Do we have the assumption that s is a pure word?

• This solution has flaws.

It could not handle some case like ("a", "*") (it crashes)

• Bralliant!!!!!!

• I've commented: This solution is assuming s has no regular expressions.

• well, the problem says: '' Matches zero or more of the preceding element. If my English is not that bad, I would believe '' must follow an element. Notice that our code is to solve a specific problem, not all problems. You may write an algorithm to EXTEND to solve a more general one.

• '*' (star) Matches zero or more of the preceding element.

• Thank you, rikimberley.
Why we need this `res[i][j] = res[i-1][j]` ? What does `res[i-1][j]` mean?