Day-21 Word Search

class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j]==word.charAt(0)  && search(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }
    
    boolean search(char[][] board, String word, int i, int j, int wordIndex) {
       
        if(i < 0  || j < 0 
           || i == board.length || j == board[0].length  
           || board[i][j] == '#' || board[i][j] != word.charAt(wordIndex)) {
                return false;
        }
   
        if(wordIndex == word.length() - 1)
            return true;
        
        char c = board[i][j];
        board[i][j] = '#';
        
        if (search(board, word, i, j+1, wordIndex+1) ||
        search(board, word, i, j-1, wordIndex+1) ||
        search(board, word, i-1, j, wordIndex+1) ||
        search(board, word, i+1, j, wordIndex+1))
            return true; 
        
        board[i][j] = c;
        return false;
    }
}