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