# My Java code, both DP and recursive

• pretty standard, nothing special. maybe the only thing to note is to let the "empty string vs ...* pattern" case handle itself , by setting the starting point of i=0 instead of 1 (which would not consider empty strings)

``````public class Solution {
public boolean isMatch(String s, String p) {
char [] ss = s.toCharArray();
char [] pp = p.toCharArray();
// return recursive(ss, 0, pp, 0);
boolean ans[][] = new boolean[ss.length+1][pp.length+1];

ans[0][0] = true; // empty string empty pattern
for(int i=0;i<=ss.length;i++) {
//default ans[i][0] = false; for all i > 0 //  non-empty string, empty pattern
for(int j=1;j<=pp.length;j++) {
if (pp[j-1] != '*' ) {
ans[i][j] = i > 0 && matches(ss[i-1], pp[j-1]) && ans[i-1][j-1];
} else {
ans[i][j] = j >=2 && (
ans[i][j-2] ||
(i > 0 && matches(ss[i-1], pp[j-1  -1])  && ans[i-1][j])
);
}
}
}
return ans[ss.length][pp.length];
}

boolean recursive(char[] s, int i, char[] p, int j) {
if (i == s.length && j == p.length) return true;
if (j == p.length) return false;

if (j< p.length-1 && p[j+1] == '*') {

return recursive(s, i, p, j+2) || i < s.length  && matches(s[i],p[j]) && recursive(s, i+1, p, j);

} else
return  i < s.length && matches(s[i], p[j]) && recursive(s,i+1, p, j+1);
}

boolean matches(char c, char p) {
if (p == '.') return true;
else return c == p;
}
}``````

• What would be the result for 'recursive' if s is "a" and b is "*a" ?

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