Word Search in 2D Board

Problem Statement

Given a 2D board of characters and a word, determine if the word exists in the grid. The word must be constructed from adjacent cells (horizontally or vertically), without reusing any cell. This medium-level problem uses backtracking to explore all paths in the grid—like a treasure hunt through a maze of letters!

Example

Input: board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "ABCCED"

Output: true (path: A→B→C→C→E→D)

Input: board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "SEE"

Output: true (path: S→E→E)

Input: board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "ABCB"

Output: false (no valid path without reuse)

Code

public 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 (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int i, int j, int index) {
        if (index == word.length()) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
            return false;
        }
        char temp = board[i][j];
        board[i][j] = '#'; // Mark as visited
        boolean found = dfs(board, word, i+1, j, index+1) ||
                        dfs(board, word, i-1, j, index+1) ||
                        dfs(board, word, i, j+1, index+1) ||
                        dfs(board, word, i, j-1, index+1);
        board[i][j] = temp; // Backtrack
        return found;
    }
}
            

def exist(board, word):
    def dfs(i, j, index):
        if index == len(word):
            return True
        if (i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or 
            board[i][j] != word[index]):
            return False
        temp = board[i][j]
        board[i][j] = "#"  # Mark as visited
        found = (dfs(i+1, j, index+1) or
                 dfs(i-1, j, index+1) or
                 dfs(i, j+1, index+1) or
                 dfs(i, j-1, index+1))
        board[i][j] = temp  # Backtrack
        return found
    
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(i, j, 0):
                return True
    return False

# Example usage
board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]]
print(exist(board, "ABCCED"))  # True
print(exist(board, "SEE"))     # True
print(exist(board, "ABCB"))    # False
            

function exist(board, word) {
    function dfs(i, j, index) {
        if (index === word.length) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || 
            board[i][j] !== word[index]) {
            return false;
        }
        let temp = board[i][j];
        board[i][j] = "#"; // Mark as visited
        let found = dfs(i+1, j, index+1) ||
                    dfs(i-1, j, index+1) ||
                    dfs(i, j+1, index+1) ||
                    dfs(i, j-1, index+1);
        board[i][j] = temp; // Backtrack
        return found;
    }
    
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }
    return false;
}

// Example usage
const board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]];
console.log(exist(board, "ABCCED")); // true
console.log(exist(board, "SEE"));    // true
console.log(exist(board, "ABCB"));   // false
            

Explanation

• Base Case: If index equals word length, the word is found.
• DFS: Explore all four directions (up, down, left, right) from each cell.
• Backtracking: Mark cells as visited (e.g., with '#') and restore them after exploration.
• Flow Example ("SEE"): Start at S(1,0) → E(1,1) → E(2,1), marking and unmarking along the way.
• Validation: Check boundaries and character matches before proceeding.

Note