using stack dfs java


  • 0
    W
    public class Node {
    	        int x;
    	        int y;
    	        int d;
    	        Set<String> set;
    	        public Node(int _x, int _y, int _d) {
    	        	set = new HashSet<>();
    	            x = _x;
    	            y = _y;
    	            d = _d;
    	        }
    	        public Node(int _x, int _y, int _d, Set<String> _set) {
    	        	set = new HashSet<>(_set);
    	            x = _x;
    	            y = _y;
    	            d = _d;
    	        }
    	    }
    	   
    	    public boolean exist(char[][] board, String word) {
    	        if(board == null) return word == null ? true : false;
    	        int m = board.length;
    	        int n = board[0].length;
    	        int[] dx = new int[] { 1, -1, 0, 0 };
    	        int[] dy = new int[] { 0, 0, 1, -1 };
    	        
    	        if (word == "") return true;
    	        if (m == 0 && n == 0 && word != "") return false;
    	        for (int i = 0; i < m; i++) {
    	            for (int j = 0; j < n; j++) {
    	                if (board[i][j] != word.charAt(0)) continue;
    
    	                Stack<Node> toVisit = new Stack<>();
    	                Node node = new Node(i, j, 0);
    	                node.set.add(i+"_"+j);
                        toVisit.push(node);
    
            	        while (!toVisit.empty()) {
            	            Node root = toVisit.pop();
            	            int x = root.x;
            	            int y = root.y;
            	            int k = root.d;
            	            System.out.println("[][]="+board[x][y]);
            	            Set<String> path = root.set;
            	            
            	            if (k >= word.length()-1) return true;
            	            
            	            for(int newi = 0; newi < dx.length; newi++) {
            	            	int nx = x + dx[newi];
            	            	int ny = y + dy[newi];
            	            	
            	            	String pos = nx+"_"+ny;
            	            	System.out.println("path="+pos);
                                if (nx < 0 || ny < 0 || nx >= m || ny >= n
                                	|| board[nx][ny] != word.charAt(k+1) 
                                	|| path.contains(pos)) continue;
                                System.out.println("path="+pos + "=" + board[nx][ny]);
                                Set<String> npath = new HashSet<>(path);
                                npath.add(pos);
                                toVisit.push(new Node(nx, ny, k+1, npath));
            	            }
            	        }
    	            }
    	        }
    	        return false;
    	    }

Log in to reply
 

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