LeetCode 212 ·
Hard
Word Search II
Return all dictionary words that can be formed by adjacent cells on a board.
Try it
Step through the core mechanic. The simulator below runs the trie shape this problem is built on.
Interactive · grid flood-fill
◦
~
~
~
~
~
~
~
~
~
~
stack (bottom → top)
(0,0)
seed the stack with the start cell (0,0)
BFS vs DFS, same grid.
Swap the frontier from a queue to a stack and breadth-first becomes depth-first.
Both visit exactly the same cells; only the order differs. BFS layers outward
(shortest-path / wave problems); DFS plunges down one branch (component / path problems).
The approach
Build a trie of the words, then DFS the board following trie links. The shared prefixes prune dead branches early, beating a separate search per word. Mark found words and prune leaf nodes.
| Aspect | Value |
|---|---|
| Pattern | Trie |
| Recognise it by | Find many words on a grid at once. |
| Time complexity | O(M·4·3^(L−1)) |
| Space complexity | O(Σ·L) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.