progress

~/problems / Tries

Word Search II

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~45 min

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 row r, column c; all rows have the same length.
  • The words in words are 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"]
A 3 by 4 letter grid, c a r t / o a e b / d n i s, with the traced words art, bean, care and cod, each drawn as a path of up, down, left and right steps
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.

⭐ Bonus: searching the grid separately for every word passes. Speed tests with 20,000 words, and with many words that share long beginnings, earn a star if each path of the grid is visited at most once for all words together and a path stops 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.

Topic: Trie. Prefix tree; longest-match tokenizing.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc