Word Search II
Module 20 · Tries
Problem
Given an m × n grid of lowercase letters and a list of words, return
every word from the list that can be formed by a path in the grid.
A path steps between horizontally or vertically adjacent cells and
may not reuse a cell within a single word.
Examples
Example 1
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]Output["oath","eat"]oath traces o(0,0) → a(0,1) → t(1,1) → h(2,1); eat traces
e(1,3) → a(1,2) → t(1,1). "pea" and "rain" have no such path, so
they're excluded.
Constraints
grid up to 12×12; up to 3·10⁴ words, each up to 10 letters, lowercase
a–z.
Attempt it first
You already know how to check whether one word exists in a grid — that's Word Search (Module 15): a DFS from each cell that walks the grid following the word's letters, marking cells visited (Module 16's backtracking) and unmarking on the way back. The obvious approach here is to run that once per word. Try that first — get it correct — and then ask the question this whole module has been building toward: when many words share prefixes, how much of that per-word DFS work is being repeated?