LeetCode 79 ·
Medium
Word Search
Return true if the word can be formed by a path of adjacent cells (no cell reused).
Try it
Step through the core mechanic. The simulator below runs the backtracking 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
DFS from each cell matching the next letter, marking the cell visited during recursion and restoring it on backtrack. Prune the moment a letter mismatches.
| Aspect | Value |
|---|---|
| Pattern | Backtracking |
| Recognise it by | Trace a word through adjacent grid cells. |
| Time complexity | O(M·4^L) |
| Space complexity | O(L) |
| Difficulty | Medium |
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.