Word Search
On this page
Problem statement
Given a grid of letters and a word, decide whether the word can be spelled by a path through the grid. The path moves one cell up, down, left or right at each step (no diagonals), and no cell may be used twice in the same path.
It is the standard "DFS on a grid with backtracking" question, and the base for its harder sibling Word Search II (many words, solved with a trie). Original problem: LeetCode 79.
Example

Board: Word Result
C A T S "CODE" true
O D E R "TEND" true
W E N D "DOD" false # the only D next to O can't be reused
Constraints (assumed)
- 1 ≤ rows, columns ≤ 6.
- 1 ≤ word length ≤ 15.
- Letters are upper- and lower-case English letters.
What this question tests
- Grid DFS: bounds checks, four directions, a clean base case.
- Backtracking state: marking a cell as used on the current path and un-marking it when you leave.
- Pruning: stopping as soon as a letter doesn't match, and optional early checks on letter counts.
Questions to ask first
- Can a cell be reused? (Here: no, not within one path.)
- Are diagonal moves allowed? (Here: no.)
- Is the grid allowed to be modified during the search? If not, use a separate
visitedarray. - Case sensitive? Does
amatchA?
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.