Find every dictionary word that can be formed on a letter board.
Start with the concrete trace below. It shows the state the algorithm must carry as it runs.
Problem trace
Word Search II: Follow board cells and trie children together, mark the current path in place, emit terminal words once, and prune exhausted trie branches while backtracking.
Input and goalFind every dictionary word that can be formed on a letter board.
Build the shared prefix trieInsert words oat, oath, eat, and pea. oat is terminal at t while oath continues from that same t to h.
double border complete word
Start at board (0,0)=oRoot has child o, so descend into that trie node and temporarily mark board (0,0) as visited.
osearch cursoratetheat
Extend the prefix to oaFrom (0,0), right neighbor (0,1)=a matches the o-node child a; downward e has no o-node child and returns immediately.
opath 1asearch cursortetheat
Reach terminal word oatFrom a, the direction loop checks down first: (1,1)=t matches. pop(None) removes and returns oat, so append oat exactly once.
opath 1apath 2tetsearch cursorheat
Continue the shared prefix to oathThe oat trie node still has child h. From t, down a and visited-up fail before right (1,2)=h matches and emits oath.
opath 1apath 2tetpath 3hsearch cursoreat
Restore cells and prune exhausted o branchBacktracking restores h,t,a,o. Empty h, then t, a, and o nodes are removed because both terminal markers were popped.
osearch cursoratetheat
Reject an incomplete e prefixAt (1,0)=e the trie accepts e, but adjacent o,e,t do not match required child a, so restore e without emitting.
oatesearch cursortheat
Start the viable e path at (2,0)The later e descends at the root, then right neighbor (2,1)=a follows the required child.
oatethepath 1asearch cursort
Reach terminal word eatFrom a, the direction loop checks up (1,1)=t before right; it matches, pop(None) returns eat, and append it.
oatetsearch cursorhepath 1apath 2t
Finish after restoration and pruningRestore t,a,e and prune their now-empty trie chain. Remaining root child p cannot start anywhere on the board, so pea is absent.
oatethesearch cursorat
- Recognize it
- Use a trie when many dictionary words must be searched on the same board and their prefixes can share traversal work.
- Keep true
- At each recursive call, the marked board path contains distinct adjacent cells spelling exactly the trie path to node; every emitted terminal has been removed, and every pruned trie branch can no longer produce an unseen word.
- Reuse it
- When many searches share prefixes, traverse input and trie in lockstep, encode path-local visited state reversibly, remove consumed outputs, and prune nodes only after their subtree is exhausted.
Pattern: Trie plus grid backtracking.
Simple idea: Word Search starts a separate search for one word. A trie lets all words share the same search. Stop when the current board path is not a dictionary prefix.
def _make_word_trie(words: list[str]) -> dict:
trie: dict = {}
for word in words:
node = trie
for char in word:
node = node.setdefault(char, {})
node[None] = word
return trie
def _find_words_from(
board: list[list[str]], row: int, col: int, node: dict, answer: list[str]
) -> None:
char = board[row][col]
if char not in node:
return
next_node = node[char]
word = next_node.pop(None, None)
if word:
answer.append(word)
board[row][col] = "#"
for row_step, col_step in ((1, 0), (-1, 0), (0, 1), (0, -1)):
next_row = row + row_step
next_col = col + col_step
if 0 <= next_row < len(board) and 0 <= next_col < len(board[0]):
_find_words_from(board, next_row, next_col, next_node, answer)
board[row][col] = char
if not next_node:
node.pop(char)
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
trie = _make_word_trie(words)
answer: list[str] = []
for row in range(len(board)):
for col in range(len(board[0])):
_find_words_from(board, row, col, trie, answer)
return answerCost: The trie takes space. Search time depends on the board and shared prefixes. Prefix checks remove most impossible paths early.