My Java recursive solution with explanation in comments


  • 0
    M
    // 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 {
                    parr.add(c);
                    sarr.add(false);
                }
            }
            
            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;
            }
        }
    }
    

Log in to reply
 

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