My Java recursive solution with explanation in comments

• ``````// process pattern to separate stars
// recursive processing (s index, pattern index)
// use visited[s index][p index] to mark branches to prune
public class Solution {
private String s;
private char[] p;
private boolean[] stars;
private boolean[][] visited;

public boolean isMatch(String s, String p) {
this.s = s;
preProcess(p);
visited = new boolean[s.length()][this.p.length];
return process(0, 0);
}

// remove '*' from pattern
// use boolean array to mark if a pattern char is followed by '*'
private void preProcess(String p) {
ArrayList<Character> parr = new ArrayList<>();
ArrayList<Boolean> sarr = new ArrayList<>();
for (int i=0; i<p.length(); i++) {
char c = p.charAt(i);
if (c == '*') {
sarr.set(sarr.size()-1, true);
} else {
}
}

this.p = new char[parr.size()];
stars = new boolean[parr.size()];
for (int i=0; i<this.p.length; i++) {
this.p[i] = parr.get(i);
stars[i] = sarr.get(i);
}
}

// i: index of s to check
// j: index of p to check
private boolean process(int i, int j) {
// reached the end of s
if (i >= s.length()) {
for (; j<p.length; j++) {
if (!stars[j]) return false;
}
// reached the end of p, OR
// all remaining pattern chars are followed by '*'
return true;
}
// pattern is used up
if (j >= p.length) return false;
// visited the branch, prune it
if (visited[i][j]) return false;

if (p[j] == '.' || p[j] == s.charAt(i)) {
if (stars[j]) {
return process(i+1, j) || process(i+1, j+1) || process(i, j+1);
}
return process(i+1, j+1);
} else {
if (stars[j]) {
return process(i, j+1);
}
visited[i][j] = true;
return false;
}
}
}
``````

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