Java: Word Search

Thought Process

The solution uses DFS backtracking to search for the word in the 2D board. We start from each cell and explore all four possible directions ( up, down, left, right). A visited matrix tracks which cells we've already checked to avoid cycles. The key optimization is early termination i.e. we stop searching as soon as we find the word. For each character match, we recursively check the next character until we either find the complete word or exhaust all possibilities. 

class Solution {

    boolean isExist = false;
    public void dfs(char[][] board, String word, int[][] vis, int sr, int sc, int wordIdx){
                
        if(sr>=board.length || sr<0 || sc>=board[0].length || sc<0 || wordIdx>=word.length() || board[sr][sc]!=word.charAt(wordIdx) || vis[sr][sc]==1 || isExist==true){
            return ;
        }
            
        vis[sr][sc]=1;
        if(wordIdx==word.length()-1)
            isExist = true;

        dfs(board,word,vis,sr+1,sc,wordIdx+1);
        dfs(board,word,vis,sr-1,sc,wordIdx+1);
        dfs(board,word,vis,sr,sc+1,wordIdx+1);
        dfs(board,word,vis,sr,sc-1,wordIdx+1);
        vis[sr][sc]=0;
    }
    public boolean exist(char[][] board, String word) {
        
        int row = board.length;
        int col = board[0].length;
        int[][] vis = new int[row][col];
        
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                dfs(board,word,vis,i,j,0);
            }
        }
        return isExist;
    }
}

Code Complexity

Time Complexity: O(m*n*4^L)

Where m and n are board dimensions and L is word length. In worst case, we explore 4 directions at each step for L steps.

Space Complexity: O(m*n + L)

For the visited matrix (m*n) and recursion stack (L) where L is the word length.

Code copied!