Word Search II
Part of Practice: Build & Search Tries
You get a grid of lowercase letters (up to 12×12) and a list of up to 30,000 distinct words. Return every word that can be spelled by starting at some cell and repeatedly stepping to an up/down/left/right neighbor, using each cell at most once per word. Words are up to 10 letters long. The same word should appear in the answer only once, even if it can be traced along several paths.
Examples
- Input:
- 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" cannot be traced with adjacent steps without leaving the grid or reusing a cell.
- Input:
- board = [["a","b"],["c","d"]], words = ["abcb"]
- Output:
- []
Spelling "abcb" would need the b cell twice, but a cell can be used at most once per word.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.