Word Search - Complete Guide

Introduction

The Word Search problem is a quintessential example of Backtracking in computer science. It presents a grid of characters (often a 2D array) and asks you to determine if a specific word can be constructed by tracing a path through adjacent cells. Adjacent cells are defined as those horizontally or vertically neighboring (diagonal moves are typically not allowed unless specified otherwise).

This problem tests your ability to explore a state space, make decisions, and revert those decisions when they lead to a dead end. It is a standard interview question that appears frequently on platforms like LeetCode (Problem 79).

Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Input/Output Example

Input:

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

Output: true

Explanation: The word "ABCCED" can be traced as follows:

1. Start at (0,0) 'A'
2. Move right to (0,1) 'B'
3. Move right to (0,2) 'C'
4. Move down to (1,2) 'C'
5. Move down to (2,2) 'E'
6. Move left to (2,1) 'D'

The Backtracking Approach

Backtracking is a recursive algorithmic technique where we try to build a solution incrementally. If a partial solution fails, we "backtrack" and try a different path.

For Word Search, the strategy is Depth First Search (DFS). We start at every cell in the grid. If the cell contains the first letter of the word, we initiate a DFS to find the rest of the letters.

Key Principles

1. Path Exploration: We explore all four possible directions (Up, Down, Left, Right) from the current cell.
2. Visited State: To prevent reusing the same cell in the current path, we must mark the cell as visited.
3. Backtracking (Unmarking): Once we have explored all paths from a cell (or hit a dead end), we must unmark the cell as visited. This allows other paths starting from different cells to use this cell.

Step-by-Step Algorithm

1. Iterate through the Grid: Loop through every cell (i, j) in the board.
2. Check Match: If board[i][j] matches the first character of word, initiate the search.
3. DFS Function (dfs(i, j, k)):

• Base Case: If k equals the length of word, we have found the entire word. Return true.
• Boundary Check: If i or j is out of bounds, or if board[i][j] does not match word[k], return false.
• Mark Visited: Temporarily change board[i][j] to a special character (e.g., # or a non-alphabetic symbol) to indicate it is used.
• Explore Neighbors: Recursively call dfs for the four adjacent cells (up, down, left, right) with k + 1.
• Backtrack: If any neighbor returns true, propagate true up. If none return true, revert board[i][j] to its original value and return false.

Code Implementation (TypeScript)

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

    function dfs(r: number, c: number, index: number): boolean {
        // Base case: if we've matched the entire word
        if (index === word.length) return true;

        // Boundary check or character mismatch
        if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== word[index]) {
            return false;
        }

        // Mark the cell as visited
        const temp = board[r][c];
        board[r][c] = '#';

        // Explore all 4 directions
        const found = 
            dfs(r + 1, c, index + 1) || // Down
            dfs(r - 1, c, index + 1) || // Up
            dfs(r, c + 1, index + 1) || // Right
            dfs(r, c - 1, index + 1);   // Left

        // Backtrack: restore the cell to its original value
        board[r][c] = temp;

        return found;
    }

    // Try to start the search from every cell
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (dfs(i, j, 0)) {
                return true;
            }
        }
    }

    return false;
}

Complexity Analysis

Time Complexity: O(N * 3^L)

• N: The number of cells in the board (m * n).
• L: The length of the word.
• Explanation: In the worst case, we might start the search from every cell (N). For each starting cell, we perform a DFS. In the DFS, at each step, we have at most 4 neighbors. However, since we cannot go back to the cell we just came from, we effectively have 3 choices per step. Therefore, the time complexity is proportional to 3^L.

Space Complexity: O(L)

• Explanation: The space complexity is determined by the recursion stack. The maximum depth of the recursion is equal to the length of the word L. We do not use additional data structures proportional to the grid size for the visited state (we modify the board in place).

Edge Cases & Validation

1. Empty Board: If board is empty or board[0] is empty, return false immediately.
2. Empty Word: If word is an empty string, return true (vacuously true, though this depends on specific problem constraints).
3. Word Longer than Board: If the length of the word is greater than the total number of cells, return false immediately.
4. Single Character Word: The algorithm handles this naturally. If word.length is 1, the base case index === word.length is met immediately after the first character match check.

Optimization: Using a Trie (Prefix Tree)

The standard backtracking solution works well for finding a single word. However, if you need to find multiple words in the same board, a Trie is highly efficient.

1. Build a Trie: Insert all words into a Trie structure.
2. Traverse the Board: Iterate through every cell on the board.
3. DFS with Trie: If the current cell's character exists in the Trie, start a DFS. As you traverse the board, move down the Trie nodes. If you reach a node marked as the end of a word, add it to the result list.

This optimization reduces the search space significantly because you prune paths in the Trie that do not match any word prefix, rather than trying to match the full word every time.

Common Mistakes to Avoid

1. Not Backtracking: Forgetting to restore the board cell value after the recursive call. This causes the algorithm to think the cell is still visited, leading to infinite recursion or false negatives.
2. Incorrect Direction Handling: Forgetting to check boundaries (r < 0 or r >= rows) before accessing the array, which throws an IndexOutOfBounds error.
3. Modifying the Original Board: While modifying the board is a valid optimization for space, ensure you restore it if you are not using a separate visited matrix. If the problem requires the board to remain unchanged, you must create a visited boolean matrix of the same size.

Summary

Word Search is a perfect problem to master Backtracking. It teaches you how to manage state during recursion, handle path constraints, and optimize space by modifying input data structures in place. Remember the mantra: Mark, Explore, Unmark.