Blind 75 Visualized

#41 · Tries

Word Search II

Given an m × n board of letters and a list of words, return every word that can be built from letters of sequentially adjacent cells (up, down, left, right), using each cell at most once per word.

HardLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Trie of the dictionary

All words share one tree of letters. While the board search extends a path one cell at a time, a trie node tells you in O(1) whether any word can still continue from this path, and the last node of each word stores the word.

Memory layout

Nodes with a letter-to-child table; each word end holds the full word so the search never has to rebuild strings. The total size is at most the sum of word lengths.

OperationCost
buildO(total letters)
board searchO(m·n·3^(L-1)) worst case, L = longest word; far less with pruning

Backtracking with in-place marks

A depth-first search that marks the current cell as used (here by overwriting it with "#"), explores the four neighbours, then restores the cell so other paths can use it again.

Memory layout

No visited array: the board itself is the mark. The recursion stack is at most the longest word long.

OperationCost
extra spaceO(L) recursion + O(trie)

Why it fits

  • Searching each word separately repeats the same board walks for words that share a prefix. A trie lets one walk serve all words at once.
  • The trie answers "can this path still become a word?" immediately, so hopeless paths are cut after one letter instead of exploring up to 3 neighbours per step.
  • Marking cells in place and restoring them gives exactly the "no cell twice per word" rule with no extra memory.

Why alternatives degrade

Word Search I once per word:
Total cost is words × board search. With thousands of words on a 12×12 board that is far too slow.
Set of prefixes:
Prunes correctly but needs a string concatenation and a hash per step; the trie moves a pointer instead.
Searching words from the end:
Does not change the number of paths, only the direction.

Four approaches, from naive to production

1 · beginner

Run Word Search I for every word

time O(W · m · n · 3^(L-1))space O(L)

For each word, try a depth-first search from every cell, matching one letter per step and marking cells as used. Collect the words that can be built.

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    int rows = board.size(), cols = board[0].size();
    string word;
    function<bool(int, int, int)> dfs = [&](int r, int c, int k) -> bool {
        if (k == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        if (board[r][c] != word[k]) return false;
        char saved = board[r][c];
        board[r][c] = '#';
        bool found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
        board[r][c] = saved;
        return found;
    };
    auto exists = [&]() -> bool {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(r, c, 0)) return true;
            }
        }
        return false;
    };
    vector<string> result;
    for (const string& w : words) {
        word = w;
        if (exists()) result.push_back(w);
    }
    return result;
}

Flaws & bottlenecks

  • Each word triggers a full scan of the board, so work scales with the number of words.
  • Words that share a prefix (like "oath" and "oats") repeat the same board walks.
  • There is no early termination across words.

Interviewer cross-questions

Why does the search branch into at most 3 directions after the first step?

Say: The cell you just came from is marked as used, so only 3 neighbours remain. The first step has 4.

Why must the cell be restored after the recursion?

Say: Backtracking: another path (or the next start cell) may use that cell. Without restoring, one failed attempt would permanently block cells.

How would you avoid repeating work across words?

Say: Search the board once and track which dictionary prefixes the current path matches. A trie is the structure that does this cheaply.

2 · intermediate

One search, pruned by a set of prefixes

time O(m · n · 3^(L-1)) worst case, much less with pruningspace O(total letters²) for the prefix set

Precompute every prefix of every word in a hash set. Run one depth-first search from every cell, growing a path string; stop as soon as the path is not a known prefix, and record it when it is a whole word.

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    unordered_set<string> wordSet(words.begin(), words.end());
    unordered_set<string> prefixes;
    for (const string& w : words) {
        for (int i = 1; i <= (int)w.size(); i++) prefixes.insert(w.substr(0, i));
    }
    int rows = board.size(), cols = board[0].size();
    set<string> found;
    function<void(int, int, string)> dfs = [&](int r, int c, string path) {
        if (r < 0 || c < 0 || r >= rows || c >= cols) return;
        char ch = board[r][c];
        if (ch == '#') return;
        string next = path + ch;
        if (!prefixes.count(next)) return;
        if (wordSet.count(next)) found.insert(next);
        board[r][c] = '#';
        dfs(r + 1, c, next);
        dfs(r - 1, c, next);
        dfs(r, c + 1, next);
        dfs(r, c - 1, next);
        board[r][c] = ch;
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) dfs(r, c, "");
    }
    return vector<string>(found.begin(), found.end());
}

Flaws & bottlenecks

  • Every step builds a new string and hashes it.
  • The prefix set stores each prefix as its own string: memory is quadratic in word length.
  • Dead branches are rediscovered from every start cell, since nothing is ever removed.

Interviewer cross-questions

Why is a set of prefixes enough to prune?

Say: If the current path is not a prefix of any word, no extension can be a word, so exploring further is pointless.

What does the result set do?

Say: The same word can be traced along several paths. A set keeps each word once.

How is a trie better here?

Say: It replaces the string building and hashing with following one pointer, and it shares the storage of common prefixes.

3 · advanced

Trie + one depth-first search

time O(m · n · 3^(L-1)) worst case, bounded by the triespace O(total letters + L)

Build a trie of the words; each word-ending node stores its word. Search the board once: carry the current trie node, move to the child for the board letter, report a word when the node holds one (then clear it to avoid duplicates), and backtrack.

struct Node {
    unordered_map<char, Node*> kids;
    string word; bool has = false;
};
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    Node* root = new Node();
    for (const string& w : words) {
        Node* node = root;
        for (char ch : w) {
            if (!node->kids.count(ch)) node->kids[ch] = new Node();
            node = node->kids[ch];
        }
        node->word = w; node->has = true;
    }
    int rows = board.size(), cols = board[0].size();
    vector<string> result;
    function<void(int, int, Node*)> dfs = [&](int r, int c, Node* node) {
        if (r < 0 || c < 0 || r >= rows || c >= cols) return;
        char ch = board[r][c];
        auto it = node->kids.find(ch);
        if (ch == '#' || it == node->kids.end()) return;
        Node* next = it->second;
        if (next->has) {
            result.push_back(next->word);
            next->has = false;
        }
        board[r][c] = '#';
        dfs(r + 1, c, next);
        dfs(r - 1, c, next);
        dfs(r, c + 1, next);
        dfs(r, c - 1, next);
        board[r][c] = ch;
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) dfs(r, c, root);
    }
    return result;
}

Flaws & bottlenecks

  • Exhausted branches stay in the trie, so later start cells still walk into them.
  • Every call re-checks the board bounds, even for neighbours that are obviously outside.
  • A dense board with a large dictionary can still explore a huge number of paths.

Interviewer cross-questions

Why store the word in the node instead of rebuilding the path?

Say: It avoids creating strings during the search: reaching the node already tells you which word you matched.

Why clear the stored word after reporting it?

Say: The same word may be found again from another path or start cell. Clearing it ensures it appears once, with no result set needed.

What is the remaining inefficiency?

Say: After all words below a node have been found, that node is useless, yet later searches still enter it. Pruning such nodes fixes this.

4 · expert

Prune exhausted trie branches

time O(m · n · 3^(L-1)) worst case; shrinks as the trie is prunedspace O(total letters + L)

Same trie search, with two refinements: check bounds and the used mark before recursing so no call is wasted, and after a node has no children and no stored word, delete it from its parent. The trie shrinks as words are found, so later searches skip dead regions.

struct Node {
    unordered_map<char, Node*> kids;
    string word; bool has = false;
};
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    Node* root = new Node();
    for (const string& w : words) {
        Node* node = root;
        for (char ch : w) {
            if (!node->kids.count(ch)) node->kids[ch] = new Node();
            node = node->kids[ch];
        }
        node->word = w; node->has = true;
    }
    int rows = board.size(), cols = board[0].size();
    vector<string> result;
    function<void(int, int, Node*)> dfs = [&](int r, int c, Node* parent) {
        char ch = board[r][c];
        auto it = parent->kids.find(ch);
        if (it == parent->kids.end()) return;
        Node* node = it->second;
        if (node->has) {
            result.push_back(node->word);
            node->has = false;
        }
        board[r][c] = '#';
        if (r > 0 && board[r - 1][c] != '#') dfs(r - 1, c, node);
        if (c > 0 && board[r][c - 1] != '#') dfs(r, c - 1, node);
        if (r + 1 < rows && board[r + 1][c] != '#') dfs(r + 1, c, node);
        if (c + 1 < cols && board[r][c + 1] != '#') dfs(r, c + 1, node);
        board[r][c] = ch;
        if (node->kids.empty() && !node->has) parent->kids.erase(ch);
    };
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) dfs(r, c, root);
    }
    return result;
}

Flaws & bottlenecks

  • The input words are consumed: the trie is destroyed during the search (rebuild it for another board).
  • Mutating the board is not thread-safe, and it breaks if the board contains the "#" character.
  • The worst case is unchanged: a board full of one letter with a dictionary of long words of that letter is still expensive.

Interviewer cross-questions

Why does pruning matter so much on big inputs?

Say: Once the words under a branch are all found, every later visit to that branch is wasted work. Removing it turns repeated dead-end exploration into a single failed lookup at the parent.

Why check neighbours before the call?

Say: It removes a function call (and its frame setup) for every off-board or used neighbour, which are the majority of calls near edges and deep in paths.

How would you make this safe for reuse?

Say: Copy the board or use a separate visited grid, and build a fresh trie per call (or keep a counter of remaining words per node instead of deleting). That trades a bit of speed for safety.

Synchronized code walkthrough

Showing: Run Word Search I for every word — shares the player above; click any step to jump.

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
    int rows = board.size(), cols = board[0].size();
    string word;
    function<bool(int, int, int)> dfs = [&](int r, int c, int k) -> bool {
        if (k == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= rows || c >= cols) return false;
        if (board[r][c] != word[k]) return false;
        char saved = board[r][c];
        board[r][c] = '#';
        bool found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
        board[r][c] = saved;
        return found;
    };
    auto exists = [&]() -> bool {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(r, c, 0)) return true;
            }
        }
        return false;
    };
    vector<string> result;
    for (const string& w : words) {
        word = w;
        if (exists()) result.push_back(w);
    }
    return result;
}