Why use a trie instead of running Word Search for each word?

Running Word Search once per word repeats the same grid walks for words that share a prefix. The trie lets one DFS check every word at once, and it stops a branch the moment its letters stop being a prefix of any word.

Why clear the word after finding it?

The same word can often be spelled along more than one path. Clearing the word-end mark makes sure it is added to the answer only once. Pruning trie nodes that have no words left below them speeds things up further.

What is the time complexity?

In the worst case O(m · n · 3^L) for an m × n board and longest word length L: each cell starts a DFS, and after the first step each cell has at most three unvisited neighbours. In practice the trie cuts most branches much earlier.

Word Search II

Find every word from a list on a letter grid with one backtracking DFS per cell, guided by a trie of the words.

HardSolve on LeetCode

Problem Understanding

Word Search II: given an m × n grid of letters and a list of words, return every word that can be spelled by a path of horizontally or vertically adjacent cells, using each cell at most once per word.

Example: on the board oaan; etae; ihkr; iflv with words oath, pea, eat, rain, the answer is oath and eat.

Attempt 1: Word Search Once Per Word

Run the single-word Word Search for each word. It works, but with many words that share prefixes, like oat, oath and oaths, the same paths are walked again and again. The grid search should check every word in a single pass.

The Intuition: Let a Trie Steer the DFS

Put every word in a trie. Then run one backtracking DFS from each cell, carrying a pointer into the trie:

At a cell, move to the trie child for its letter. If there is no such child, no word continues this way: stop the branch immediately.
If that trie node ends a word, record the word and clear the mark so it is not added twice.
Mark the cell #, try its unvisited neighbours with the child node, then write the letter back.

The trie turns "is this path the start of any word?" into a single lookup, which is what prunes the search.

Interactive Walkthrough

Every cell starts a DFS in turn. Cells on the current path show #, linked in path order, and the prefix they spell is shown beside the board. A cell turns red the moment no word continues with its letter, and green when a word ends there.

Dry Run Table

Board: oaan; etae; ihkr; iflv. Words: oath, pea, eat, rain

Start	Path	Result
(0,0) `o`	o → a → t → h	found `oath`
(0,1) `a`	`a`	no word starts with `a`: stop
(1,0) `e`	e → (no `a` next to it)	stop
(1,3) `e`	e → a → t	found `eat`
(2,3) `r`	r → (no `a` next to it)	stop: `rain` is not on the board

pea is never started: there is no p on the board.

The Solution Template

A trie of the words, and a backtracking DFS from every cell that follows it.

Word Search II Code

1var findWords = function(board, words) {
2    const root = {};
3    for (const w of words) {
4        let node = root;
5        for (const ch of w) node = node[ch] ??= {};
6        node.$ = w;
7    }
8    const rows = board.length, cols = board[0].length, found = [];
9    const dfs = (r, c, node) => {
10        const ch = board[r][c];
11        const nxt = node[ch];
12        if (!nxt) return;
13        if (nxt.$) {
14            found.push(nxt.$);
15            delete nxt.$;
16        }
17        board[r][c] = '#';
18        for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
19            const nr = r + dr, nc = c + dc;
20            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') dfs(nr, nc, nxt);
21        }
22        board[r][c] = ch;
23    };
24    for (let r = 0; r < rows; r++) for (let c = 0; c < cols; c++) dfs(r, c, root);
25    return found;
26};

Edge Cases & Common Mistakes

The same word on two paths: clear the word-end mark when it is found, or the word appears twice in the answer.
Reusing a cell: mark it # before exploring and write the letter back afterwards, exactly as in Word Search.
Words that are prefixes of other words: oat and oath are both recorded on the same walk, because finding a word does not stop the DFS.
Letters not on the board: words with them are never started, at no cost.

Summary

Word Search II is Word Search with a trie in place of a single target word. One backtracking DFS per cell follows the trie, stops as soon as no word shares the current prefix, and collects every word whose end it reaches.

More practice: DSA interview questions with answers · patterns cheat sheet

Design Add and Search Words Data Structure

Prefix Matching