Maintained by Vikas Dulgunde, software engineer
You are handed a rectangular board where every cell holds one lowercase letter, plus a list of candidate words. A word is considered present on the board if you can place its letters onto a sequence of cells such that each consecutive pair of letters sits in cells that touch edge to edge (up, down, left, or right). Diagonal steps do not count.
Within a single word the same cell cannot be visited twice, but different words are checked independently, so two words may both reuse the same cell across separate searches. Your job is to collect the subset of the candidate list that the board can spell out and return those words.
The board is small (at most 12 by 12) and the candidate list is short (at most 30 words, each up to 10 letters), but a naive search that explores the board fresh for every word can repeat enormous amounts of work when words share prefixes. The interesting part of this problem is searching for all words at once.
The order of the returned words does not carry meaning; any order that contains exactly the matching words is acceptable. The reference returns them sorted for a stable result.
"oath" traces o(0,0) -> a(0,1) -> t(1,1) -> h(2,1), all edge adjacent. "eat" traces e(1,0) -> a(1,1)? no; it uses e(1,3) -> a(1,2) -> t(1,1). "pea" fails because there is no p on the board, and "rain" cannot be completed, so only the two reachable words come back.
Starting at a(0,0), step right to b(0,1), down to d(1,1), then left to c(1,0). Each move crosses a shared edge and no cell repeats, so the loop spells "abdc".
None of the letters e, f, or g appear on the board, so the search never gets past the first character and nothing is returned.
Visible test cases
Searching the whole board separately for each word repeats work whenever two words begin with the same letters. Think about a structure that lets you walk many words at the same time.
Insert all the candidate words into a trie. Then a single depth-first walk from each cell can follow trie edges, and the walk only continues while the path so far is still a prefix of some unfound word.
Mark the current cell as visited before recursing and restore it afterward so a word never reuses a cell. When you reach a trie node that ends a word, record that word and clear its marker so it is not reported twice.
Treat each candidate word as its own classic word-search problem and run a separate backtracking scan of the board for it.
Build a trie of all words so one board walk follows shared prefixes once, and prune the moment the current path is no longer a prefix of any unfound word.