Word Search II

Problem Description

Given an m × n board of characters and a list of strings words, return all words on the board.

Each word must 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 word.

Examples

Constraints

• m == board.length
• n == board[i].length
• 1 ≤ m, n ≤ 12
• board[i][j] is a lowercase English letter.
• 1 ≤ words.length ≤ 3 * 10⁴
• 1 ≤ words[i].length ≤ 10
• All strings in words are unique.

Pruning Search Branches Early with a Prefix Tree

The naive approach is doing a full grid search for each word individually. With a board of size 12x12 and 30,000 words, that is O(words * R * C * 4^L) which is far too slow. The key insight is searching for all words simultaneously by traversing the board and a prefix tree together.

Store all target words in a trie. Start a depth-first search from every cell on the board. If the current path of characters is not a prefix in the trie, stop searching immediately. This early pruning eliminates millions of dead-end paths. When a path reaches a node marked as a complete word, add that word to the result list and unmark it in the trie to prevent duplicates.

Solution 1: Trie-Guided Backtracking

Build a trie from the input words. Perform a backtracking search starting at each cell, advancing the trie pointer as you step onto adjacent cells.

import java.util.ArrayList;
import java.util.List;

class Solution {
    private class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null; // store complete word directly to avoid rebuilding path
    }

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode curr = root;
            for (char c : w.toCharArray()) {
                int idx = c - 'a';
                if (curr.children[idx] == null) curr.children[idx] = new TrieNode();
                curr = curr.children[idx];
            }
            curr.word = w;
        }

        List<String> result = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root, result);
            }
        }
        return result;
    }

    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;
        char temp = board[r][c];
        if (temp == '#' || node.children[temp - 'a'] == null) return;

        node = node.children[temp - 'a'];
        if (node.word != null) {
            result.add(node.word);
            node.word = null; // prevent duplicate entries
        }

        board[r][c] = '#'; // mark as visited
        dfs(board, r + 1, c, node, result);
        dfs(board, r - 1, c, node, result);
        dfs(board, r, c + 1, node, result);
        dfs(board, r, c - 1, node, result);
        board[r][c] = temp; // backtrack
    }
}

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None


class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        root = TrieNode()
        for w in words:
            curr = root
            for c in w:
                if c not in curr.children:
                    curr.children[c] = TrieNode()
                curr = curr.children[c]
            curr.word = w

        result = []
        rows, cols = len(board), len(board[0])

        def dfs(r, c, node):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            char = board[r][c]
            if char == "#" or char not in node.children:
                return

            next_node = node.children[char]
            if next_node.word:
                result.append(next_node.word)
                next_node.word = None  # prevent duplicate entries

            board[r][c] = "#"  # mark as visited
            dfs(r + 1, c, next_node)
            dfs(r - 1, c, next_node)
            dfs(r, c + 1, next_node)
            dfs(r, c - 1, next_node)
            board[r][c] = char  # backtrack

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)

        return result

#include <vector>
#include <string>

class Solution {
private:
    struct TrieNode {
        TrieNode* children[26] = {};
        std::string word = "";
    };

    void dfs(std::vector<std::vector<char>>& board, int r, int c, TrieNode* node, std::vector<std::string>& result) {
        if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size()) return;
        char temp = board[r][c];
        if (temp == '#' || !node->children[temp - 'a']) return;

        node = node->children[temp - 'a'];
        if (!node->word.empty()) {
            result.push_back(node->word);
            node->word = ""; // prevent duplicate entries
        }

        board[r][c] = '#'; // mark as visited
        dfs(board, r + 1, c, node, result);
        dfs(board, r - 1, c, node, result);
        dfs(board, r, c + 1, node, result);
        dfs(board, r, c - 1, node, result);
        board[r][c] = temp; // backtrack
    }

public:
    std::vector<std::string> findWords(std::vector<std::vector<char>>& board, std::vector<std::string>& words) {
        TrieNode* root = new TrieNode();
        for (const std::string& w : words) {
            TrieNode* curr = root;
            for (char c : w) {
                int idx = c - 'a';
                if (!curr->children[idx]) curr->children[idx] = new TrieNode();
                curr = curr->children[idx];
            }
            curr->word = w;
        }

        std::vector<std::string> result;
        for (int r = 0; r < board.size(); r++) {
            for (int c = 0; c < board[0].size(); c++) {
                dfs(board, r, c, root, result);
            }
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(M * (4 * 3^(L-1))) where M is the number of cells on the board, and L is the maximum length of a word. The first step has 4 choices, and subsequent steps have 3 choices.
• Space Complexity: O(N * L) where N is the number of words and L is the maximum word length, which represents the trie storage size.

Where it breaks: If there are words that have huge overlap, we still end up traversing branches. To optimize further, you can prune the trie dynamically: when a node’s children are all completely traversed and matched, you can remove the node from the parent to avoid revisiting that branch.

Why Not Do Separate Word Searches for Each Word?

Doing a grid search per word leads to redundant work. If two words share a prefix, like “oath” and “oaths”, a search-per-word checks the cells for “o-a-t-h” twice. By combining them in a trie, you search the shared prefix path only once, reducing execution times by several orders of magnitude.

Common Mistakes

• Not resetting the visited state correctly. If you fail to restore board[r][c] = temp during backtracking, other branches will be unable to use that cell.
• Adding duplicate words to the output. Set the matched trie node’s word = null (or "") immediately after adding it to the result list to guarantee uniqueness.
• Not handling the boundary checks before accessing arrays. Always check if r and c are out of bounds before checking the value at board[r][c].

Frequently Asked Questions

Does the order of coordinates in the search directions matter? No. Moving down, up, right, or left can be checked in any sequence, as long as all four cardinal directions are checked.

How do we avoid stack overflow with deep recursion? The word length constraint is 10, meaning the recursion stack depth is at most 10. Stack overflow is not a risk here.

What does this problem test in interviews? It tests your ability to optimize backtracking searches by leveraging custom prefix trees to prune search space, a concept vital in regex engines and game solving.

← All Problems