A top-down DFS solution


  • 0
    class Solution {
        private class Node{
            int si, pi;
            Node(int i, int j){
                si=i; pi=j;
            }
        }
        public boolean isMatch(String s, String p) {
            //Top-down DFS
            int m=s.length(), n=p.length();
            boolean[][] visited = new boolean[m+1][n+1];
            Stack<Node> stack = new Stack<>();
            stack.push(new Node(0,0));
            while(!stack.isEmpty()){
                Node node=stack.pop();
                int si = node.si, pi = node.pi;
                visited[si][pi]=true;
                if(pi>=n){
                    if(si>=m) return true;
                    continue;
                }
                boolean match = (!(si>=m)&&(s.charAt(si)==p.charAt(pi)||p.charAt(pi)=='.'));
                if(pi<n-1&&p.charAt(pi+1)=='*'){
                    if(!visited[si][pi+2]) 
                        stack.push(new Node(si, pi+2));
                    if(match&&!visited[si+1][pi]) 
                        stack.push(new Node(si+1, pi));
                }else if(match&&!visited[si+1][pi+1])
                    stack.push(new Node(si+1, pi+1));
            }
            return false;
        }
    }
    

Log in to reply
 

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