# BackTracking Explained

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

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