Word Search: Multiple Solutions and Complexity Analysis

Introduction to Word Search Algorithms

The Word Search problem is a classic algorithmic challenge frequently encountered in coding interviews and competitive programming. Given a 2D grid of characters and a target word, the task is to determine whether the 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 in a single word construction.

While the standard Word Search problem asks whether a single word exists, a more interesting variant involves finding multiple solutions — either multiple occurrences of the same word, or searching for multiple words simultaneously. This variant introduces unique challenges in terms of algorithm design, state management, and computational complexity.

Why Multiple Solutions Matter

Understanding how to handle multiple solutions in Word Search is important for several reasons:

Real-world applications: Puzzle games, OCR verification systems, and DNA sequence analysis often require finding all occurrences of patterns, not just one.
Algorithmic depth: It forces developers to think beyond early termination and consider complete state space exploration.
Complexity awareness: Multiple solutions expose the exponential nature of backtracking, making complexity analysis essential.
Interview readiness: Many interviewers extend the basic problem to test deeper understanding.

The Core Algorithm: Backtracking with DFS

The foundation of any Word Search solution is Depth-First Search (DFS) combined with backtracking. We explore each cell as a potential starting point, then recursively try to match subsequent characters by moving to adjacent cells. If a path fails, we backtrack by unmarking visited cells and trying alternative directions.

Basic Single-Word Implementation

Let us start with the standard implementation before extending it to handle multiple solutions:

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

    function dfs(r, c, index) {
        if (index === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
        if (board[r][c] !== word[index]) return false;

        const temp = board[r][c];
        board[r][c] = '#'; // mark as visited

        const found = dfs(r + 1, c, index + 1) ||
                      dfs(r - 1, c, index + 1) ||
                      dfs(r, c + 1, index + 1) ||
                      dfs(r, c - 1, index + 1);

        board[r][c] = temp; // backtrack
        return found;
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

This implementation returns true as soon as it finds one valid path. To find multiple solutions, we need to modify this approach to continue searching even after finding a match.

Finding All Occurrences of a Single Word

To find every occurrence of a word in the grid, we collect all valid paths instead of returning early. Each solution is represented as a list of coordinates tracing the word through the grid.

function findAllOccurrences(board, word) {
    const rows = board.length;
    const cols = board[0].length;
    const results = [];

    function dfs(r, c, index, path) {
        if (index === word.length) {
            results.push([...path]);
            return;
        }
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (board[r][c] !== word[index]) return;

        const temp = board[r][c];
        board[r][c] = '#';
        path.push([r, c]);

        dfs(r + 1, c, index + 1, path);
        dfs(r - 1, c, index + 1, path);
        dfs(r, c + 1, index + 1, path);
        dfs(r, c - 1, index + 1, path);

        path.pop();
        board[r][c] = temp; // backtrack
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (board[r][c] === word[0]) {
                dfs(r, c, 0, []);
            }
        }
    }
    return results;
}

// Example usage
const board = [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
];
console.log(findAllOccurrences(board, "ABCCE"));
// Output: [[ [0,0],[0,1],[0,2],[1,2],[2,2] ]]

Notice that we no longer short-circuit on the first match. The DFS explores every possible path, and each complete match is recorded as a separate solution. The backtracking step (path.pop() and restoring board[r][c]) ensures that cells become available again for other potential paths.

Searching for Multiple Words Simultaneously

A more advanced variant involves searching for a list of words at once. A naive approach runs the single-word search for each word independently. However, this is inefficient when words share common prefixes. A Trie data structure dramatically improves performance by allowing us to share prefix exploration across multiple words.

Trie-Based Multi-Word Search

class TrieNode {
    constructor() {
        this.children = {};
        this.word = null; // stores complete word at terminal node
    }
}

function buildTrie(words) {
    const root = new TrieNode();
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.word = word;
    }
    return root;
}

function findWords(board, words) {
    const rows = board.length;
    const cols = board[0].length;
    const root = buildTrie(words);
    const results = [];

    function dfs(r, c, node, path) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (board[r][c] === '#') return;

        const char = board[r][c];
        if (!node.children[char]) return;

        const nextNode = node.children[char];
        path.push([r, c]);

        if (nextNode.word) {
            results.push({
                word: nextNode.word,
                path: [...path]
            });
            nextNode.word = null; // avoid duplicate matches
        }

        const temp = board[r][c];
        board[r][c] = '#';

        dfs(r + 1, c, nextNode, path);
        dfs(r - 1, c, nextNode, path);
        dfs(r, c + 1, nextNode, path);
        dfs(r, c - 1, nextNode, path);

        board[r][c] = temp;
        path.pop();
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            dfs(r, c, root, []);
        }
    }
    return results;
}

// Example usage
const grid = [
    ['o', 'a', 'a', 'n'],
    ['e', 't', 'a', 'e'],
    ['i', 'h', 'k', 'r'],
    ['i', 'f', 'l', 'v']
];
const words = ["oath", "pea", "eat", "rain"];
console.log(findWords(grid, words));
// Output: [{ word: 'oath', path: [...] }, { word: 'eat', path: [...] }]

The Trie approach is powerful because a single DFS traversal from each cell can match multiple words simultaneously. When the current character does not lead to any Trie child, we prune the search immediately. Setting nextNode.word = null after recording a match prevents duplicate entries for the same word.

Complexity Analysis

Understanding the computational complexity of Word Search with multiple solutions is critical for writing efficient code and predicting performance on larger inputs.

Single Word Search

For a board of size m × n and a word of length L:

Time Complexity: O(m × n × 4^L) in the worst case. We start DFS from each of the m × n cells. At each step, we explore up to 4 directions. The recursion depth is at most L.
Space Complexity: O(L) for the recursion stack, plus O(m × n) if using a separate visited matrix instead of in-place marking.

In practice, the actual runtime is much lower because most paths terminate early when characters do not match. However, worst-case grids filled with the same character (e.g., all 'A's) and a word like "AAAAA" will hit the theoretical bound.

Multiple Occurrences of a Single Word

When finding all occurrences, the time complexity remains O(m × n × 4^L) because we must explore the entire search space without early termination. The space complexity increases to O(m × n × 4^L) in the worst case for storing all solutions, though this is bounded by the actual number of valid paths, which is typically much smaller.

Multiple Words with Trie

For k words with total character count K (sum of all word lengths):

Trie Construction: O(K) time and space.
Search Time: O(m × n × 4^L_max) where L_max is the length of the longest word. The Trie prunes branches early, so the effective branching factor is reduced when words share prefixes.
Space Complexity: O(K) for the Trie plus O(L_max) for the recursion stack.

Compared to running k independent searches — which would cost O(k × m × n × 4^L_max) — the Trie approach provides significant savings, especially when the word list contains many overlapping prefixes.

Best Practices

Use In-Place Marking for Visited Cells

Instead of maintaining a separate 2D visited array, temporarily modify the board cell to a sentinel value (like '#') and restore it during backtracking. This reduces space overhead and improves cache locality.

Prune Early with Character Frequency Checks

Before starting the search, verify that the board contains enough of each character required by the word. If the word requires three 'Z's but the board only has two, you can return immediately without any DFS.

function canPossiblyExist(board, word) {
    const freq = {};
    for (const row of board) {
        for (const char of row) {
            freq[char] = (freq[char] || 0) + 1;
        }
    }
    for (const char of word) {
        if (!freq[char]) return false;
        freq[char]--;
    }
    return true;
}

Optimize Search Direction

If the word has more occurrences of its last character than its first character on the board, search the reversed word instead. This reduces the number of starting points and prunes more aggressively.

Avoid Duplicate Solutions Carefully

When collecting multiple solutions, ensure your deduplication strategy is correct. For the Trie approach, nullifying node.word after a match prevents the same word from being recorded twice. For single-word multiple-occurrence searches, each distinct path is a unique solution by definition, so no deduplication is needed.

Consider Iterative Deepening for Very Long Words

If the target word is extremely long, deep recursion may cause stack overflow. An iterative approach using an explicit stack can mitigate this, though it complicates backtracking logic.

Common Pitfalls

Forgetting to restore the board: If you mark a cell as visited but forget to unmark it during backtracking, subsequent paths will incorrectly skip that cell.
Modifying shared path arrays without copying: When storing solutions, always push a copy of the path array ([...path]) rather than a reference, since the original array continues to mutate during backtracking.
Ignoring diagonal movement requirements: The standard problem only allows horizontal and vertical movement. If diagonals are allowed, the branching factor increases from 4 to 8, significantly affecting complexity.
Not handling empty inputs: Always validate that the board and word are non-empty before proceeding with the search.

Conclusion

The Word Search problem with multiple solutions is a rich algorithmic exercise that combines backtracking, graph traversal, and trie-based optimization. By extending the basic DFS approach to collect all valid paths and leveraging tries for multi-word searches, developers can build efficient solutions that scale to larger grids and word lists. Understanding the complexity trade-offs — particularly the exponential nature of the search space and how prefix sharing reduces effective branching — is essential for writing performant code. With careful attention to backtracking correctness, early pruning, and deduplication strategies, you can confidently tackle Word Search variants in both interviews and production applications.