# A top-down DFS solution

• 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;
}
}
``````

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