BackTracking Explained


  • 0
    K
    public class Solution {
        public boolean exist(char[][] board, String word) {
            // Maintain matrix of visited nodes
            boolean[][] visited = new boolean[board.length][board[0].length];
            // Start from every possible node
            for(int k=0; k < board.length; k++) {
                for(int l=0; l < board[0].length; l++) {
                    if(wordSearch(word.toCharArray(), 0, board, k, l, visited)) {
                        return true;
                    }
                }
            }
            return false;
        }
        
        private boolean wordSearch(char[] word, int i, char[][] board, int r, int c, boolean[][] visited) {
            // If the node is visited already, return
        	if(visited[r][c] == true) return false;    	
            // If the character does not match, return
            if(i<word.length && word[i] != board[r][c]) return false;
            // Else, character matched. Mark the node as visited
            visited[r][c] = true;
            // If this is the last character, no more recursion. return true
            if(i+1==word.length) return true;      
            //Else, start looking for next character in all directions starting from this point          
            boolean fwd=false,bckwrd=false,down=false,up=false;
            if(r<board.length-1) {
                fwd = wordSearch(word, i+1, board, r+1, c, visited);
            }
            if(r>0) {
                bckwrd = wordSearch(word, i+1, board, r-1, c, visited);
            }
            if(c<board[0].length-1) {
                down = wordSearch(word, i+1, board, r, c+1, visited);
            }
            if(c>0) {
                up = wordSearch(word, i+1, board, r, c-1, visited);
            }
            // If the word is found in any of the four directions, return true
            if(fwd || bckwrd || down || up) return true;
            // Otherwise, mark node as unvisited since it can be visited by other nodes and return false since there was no match so far
            visited[r][c] = false;
            return false;
        }
    }
    

Log in to reply
 

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