Word Search II
Maintained by Vikas D, software engineer
You are handed a rectangular board where every cell holds one lowercase letter, plus a list of candidate words. A word is considered present on the board if you can place its letters onto a sequence of cells such that each consecutive pair of letters sits in cells that touch edge to edge (up, down, left, or right). Diagonal steps do not count.
Within a single word the same cell cannot be visited twice, but different words are checked independently, so two words may both reuse the same cell across separate searches. Your job is to collect the subset of the candidate list that the board can spell out and return those words.
The board is small (at most 12 by 12) and the candidate list is short (at most 30 words, each up to 10 letters), but a naive search that explores the board fresh for every word can repeat enormous amounts of work when words share prefixes. The interesting part of this problem is searching for all words at once.
The order of the returned words does not carry meaning; any order that contains exactly the matching words is acceptable. The reference returns them sorted for a stable result.
Examples
"oath" traces o(0,0) -> a(0,1) -> t(1,1) -> h(2,1), all edge adjacent. "eat" traces e(1,0) -> a(1,1)? no; it uses e(1,3) -> a(1,2) -> t(1,1). "pea" fails because there is no p on the board, and "rain" cannot be completed, so only the two reachable words come back.
Starting at a(0,0), step right to b(0,1), down to d(1,1), then left to c(1,0). Each move crosses a shared edge and no cell repeats, so the loop spells "abdc".
None of the letters e, f, or g appear on the board, so the search never gets past the first character and nothing is returned.
Constraints
- m == board.length, n == board[i].length, 1 <= m, n <= 12
- Every board cell is a lowercase English letter
- 1 <= words.length <= 30
- 1 <= words[i].length <= 10, each word is lowercase English letters
- All words in the list are unique
Visible test cases
- findWords([["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], ["oath","pea","eat","rain"]) == ["eat","oath"]
- findWords([["a","b"],["c","d"]], ["abdc"]) == ["abdc"]
- findWords([["a"]], ["a"]) == ["a"]
- findWords([["a","b"],["c","d"]], ["abdc","cdba"]) == ["abdc","cdba"]
- findWords([["a","b"],["c","d"]], ["efg"]) == []
Hints
Hint 1
Searching the whole board separately for each word repeats work whenever two words begin with the same letters. Think about a structure that lets you walk many words at the same time.
Hint 2
Insert all the candidate words into a trie. Then a single depth-first walk from each cell can follow trie edges, and the walk only continues while the path so far is still a prefix of some unfound word.
Hint 3
Mark the current cell as visited before recursing and restore it afterward so a word never reuses a cell. When you reach a trie node that ends a word, record that word and clear its marker so it is not reported twice.
Approaches
Independent DFS per word
Time O(W * m * n * 4^L) where W is the number of words and L the maximum word length · Space O(L) for the recursion stackTreat each candidate word as its own classic word-search problem and run a separate backtracking scan of the board for it.
- For each word, try every cell as a possible first letter.
- From a matching start, recurse into the four neighbors looking for the next character, marking cells visited so the path never reuses one.
- If the full word is matched, add it to the result and move on to the next word.
- Restore visited markers as the recursion unwinds.
Trie plus single shared DFS
Time O(m * n * 4 * 3^(L-1)) for the board walk plus O(total characters) to build the trie; the 3 comes from never stepping back to the cell you arrived from · Space O(total characters in all words) for the trie plus O(L) recursion depthBuild a trie of all words so one board walk follows shared prefixes once, and prune the moment the current path is no longer a prefix of any unfound word.
- Insert every word into a trie, storing the full word at the node where it ends.
- Start a DFS from each cell, passing the trie root as the current node.
- At a cell, look up its letter among the current trie node's children; if absent, stop this branch immediately.
- If the child node marks the end of a word, append that word to the answer and clear its end marker to avoid duplicates.
- Mark the cell visited, recurse into the four orthogonal neighbors with the child node, then restore the cell.
Common mistakes
- Reporting the same word twice when it can be spelled by more than one path. Clear the word marker (or remove it from the trie) the first time you find it.
- Forgetting to restore a cell's letter after recursion, which corrupts the board for later starts. Always undo the visited marker on the way out.
- Re-scanning the board once per word instead of walking all words together with a trie; this is what makes the brute force blow up on shared prefixes.
- Using a separate visited matrix but never resetting it between starting cells, so later searches see stale visited flags.
- Allowing diagonal moves. Only the four edge-adjacent neighbors are valid steps.
Follow-up variations
- Prune the trie as words are found by deleting leaf nodes, so the search space shrinks and dead branches stop being explored.
- Return the actual cell path for each found word, not just the word string.
- Handle a streaming board or a board too large to keep visited flags for, where you cannot mutate cells in place.
- Extend adjacency to eight directions including diagonals and adjust the neighbor generation.