A top-down DFS solution


  • 0

    The idea is similar to my solution of #10. Regular Expression Matching: https://discuss.leetcode.com/topic/114838/a-top-down-dfs-solution

    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();
            int n = p.length();
            Stack<Node> stack = new Stack<>();
            boolean[][] visited = new boolean[m+1][n+1];
            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;
                }
                if(p.charAt(pi)=='*'){
                    if(si<m){
                        if(!visited[si+1][pi])
                            stack.push(new Node(si+1, pi));
                        if(!visited[si+1][pi+1])
                            stack.push(new Node(si+1, pi+1));
                    }
                    if(!visited[si][pi+1])
                        stack.push(new Node(si, pi+1));
                }else if(si<m&&(s.charAt(si)==p.charAt(pi)||p.charAt(pi)=='?')){
                    if(!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.