Word Search medium

Problem Statement

Given an m x n board and a word word, find if the word exists in the grid.

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

Example 1:

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

Example 2:

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

Steps

  1. Depth-First Search (DFS): We'll use DFS to explore the board. DFS is ideal for traversing connected components, which is exactly what we need to check if the word exists.

  2. Base Cases:

    • If the word is empty, return true (we've found it!).
    • If we're out of bounds, or the current character doesn't match the next letter in the word, return false.

  3. Recursive Step:

    • Mark the current cell as visited (to avoid cycles).
    • Recursively explore the four adjacent cells.
    • If any recursive call returns true, we've found the word.
    • Unmark the current cell (backtrack) before returning false.

Explanation

The solution uses DFS to explore all possible paths on the board. Each recursive call explores one possible path. The key is to mark cells as visited to avoid revisiting the same cell in a path and correctly backtrack by unmarking visited cells. If a recursive call successfully finds the word, it immediately returns true. If not, we explore the other paths. If no path leads to the full word, the function returns false.

Code

function exist(board: string[][], word: string): boolean {
    const rows = board.length;
    const cols = board[0].length;

    const dfs = (row: number, col: number, wordIndex: number): boolean => {
        // Base cases
        if (wordIndex === word.length) return true; // Word found
        if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] !== word[wordIndex]) return false;

        const originalChar = board[row][col];
        board[row][col] = '#'; // Mark as visited

        // Explore adjacent cells
        const found = dfs(row + 1, col, wordIndex + 1) ||
                      dfs(row - 1, col, wordIndex + 1) ||
                      dfs(row, col + 1, wordIndex + 1) ||
                      dfs(row, col - 1, wordIndex + 1);

        board[row][col] = originalChar; // Backtrack: Unmark
        return found;
    };

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }

    return false;
};

Complexity

  • Time Complexity: O(M * N * 4L), where M and N are the dimensions of the board and L is the length of the word. In the worst-case scenario, we might explore all possible paths. The 4L comes from exploring four directions at each step in the word.

  • Space Complexity: O(L) due to the recursive call stack (depth of recursion is at most L) and the space used to mark visited cells in the board (this is O(M*N) in the worst case, but is often a lot smaller). The space complexity is dominated by the recursive calls.