Given a grid of letters and a word, return whether the word can be built from letters of sequentially adjacent cells (horizontally or vertically), using each cell at most once.
Before you code
From each starting cell, the search walks to neighbors whose letter matches the next character. The cell must be marked as used while it is part of the path, and unmarked when the search backs out of it, or other paths can't use it.
Hints
- Write
dfs(r, c, k): does the word from index k start at (r, c)? - Fail fast on out-of-bounds, a used cell or a mismatched letter.
- Mark the cell (for example, replace it with
#), try the four neighbors withk + 1, then restore the letter. - Prune: if the board has fewer of some letter than the word needs, return false before searching.
Production & complexity notes
When solving Word search on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Backtracking basics to reinforce the underlying pattern.
What it practices
The choose, explore, unchoose pattern and pruning, from Backtracking basics.