## Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of a sequentially adjacent cells, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

```board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.```
```class Solution {
boolean[][] visited_node;
public boolean exist(char[][] board, String word) {
if(board == null || word == null || word.length() == 0) return false;
int heightOfBoard = board.length;
int widthOfBoard = board[0].length;
if(heightOfBoard == 0 || widthOfBoard == 0) return false;
visited_node = new boolean[heightOfBoard][widthOfBoard];
for(int i = 0 ;  i< heightOfBoard ; i++){
for(int j = 0 ; j < widthOfBoard ; j++){
if(board[i][j] == word.charAt(0) && canWordFormed(board,word,i,j,0)){
return true;
}
}
}
return false;
}

private boolean canWordFormed(char[][] board,String word,int i, int j, int indexOfWord){
if(indexOfWord == word.length()){
return true;
}
int heightOfBoard = board.length;
int widthOfBoard = board[0].length;
// breaking condition;
if( i < 0 || i >= heightOfBoard || j < 0 || j >= widthOfBoard
|| board[i][j] != word.charAt(indexOfWord) || visited_node[i][j]){
return false;
}
visited_node[i][j] = true;
if(
canWordFormed(board,word, (i-1),j, indexOfWord+1) ||
canWordFormed(board,word, (i+1),j, indexOfWord+1) ||
canWordFormed(board,word, i,(j-1), indexOfWord+1) ||
canWordFormed(board,word, i,(j+1), indexOfWord+1))
{
return true;
}
visited_node[i][j] = false;
return false;
}
}```

Algorithm