A word-puzzle app hands you a grid of letters and a long list of candidate words, and wants to know which candidates can be traced in the grid.
A word can be traced if you can start on some cell holding its first letter and step to a cell up, down, left or right (no diagonals) for each following letter, never using the same cell twice within that word.
Write find_words(rows: list[str], words: list[str]) -> list[str] that returns every word of words that can be traced, sorted alphabetically.
rows[r][c]is the letter in rowr, columnc; all rows have the same length.- The words in
wordsare all different. Different words may reuse the same cells.
find_words(["cart",
"oaeb",
"dnis"], ["cat", "care", "coat", "bean", "dais", "art", "cod"])
# ["art", "bean", "care", "cod"]
find_words(["ab",
"cd"], ["abdc", "abcd", "aba", "ad"])
# ["abdc"] ("abcd" would need a diagonal step, "aba" reuses a cell)
find_words(["x"], ["x", "xx"]) # ["x"]
Constraints: the grid has 1 to 12 rows and 1 to 12 columns; up to 2 * 10^4 words, each 1 to 10 letters long. Everything uses a-z.
Searching the grid separately for every word repeats the same work over and over: when many words start the same way, a single walk over the grid should serve all of them. Aim to visit each path of the grid at most once for all words together, and to stop a path as soon as no remaining word starts with it.
Show hint
load the words into one shared structure before touching the grid, so that one depth-first walk can follow every word at once. Removing words once they're found keeps later walks short.