Word Search
Given a grid of letters and a word, determine whether the word can be spelled by a path of horizontally or vertically adjacent cells, using each cell at most once.
- 1 ≤ m, n ≤ 6
- 1 ≤ word.length ≤ 15
- Letters only
- Path through a grid with a no-reuse rule
- Extend the path one letter at a time and undo on failure
- Small grid — exhaustive search with pruning
Enumerating every arrangement is exponential, so tiny bounds plus "all" or "any valid" wording mean search the decision tree: choose, recurse, un-choose. Pruning invalid partial states early (a queen already attacked, a sum already exceeded) is what makes it practical.
For every cell matching the first letter, start a DFS that matches word[i] at the current cell, temporarily marks the cell as visited, and tries the four neighbours for word[i + 1]. Restore the cell before returning so other paths can reuse it. Return true as soon as the full word is matched. Marking in place avoids a separate visited grid.
- Prune early by checking letter frequencies in the grid against the word. For many words on one board, use a trie (Word Search II).