Pattern Recognition Drill

#109 — Word Search II

Hard Tries

The Problem

Given a board of characters and a list of words, find all words that can be formed by adjacent cells.

What approach would you use?

Think about it before scrolling down.

Key Signals

'Multiple words on a board' → build trie from word list, DFS on board
'Adjacent cells' → backtracking, 'list of words' → trie beats checking each word separately

Trie

Build trie from words. DFS from each cell, walking the trie simultaneously. Prune when no trie child. O(m*n*4^L).

Alt: Backtracking

For each word, backtrack on board. Works but repeats work across words. O(W*m*n*4^L).

Common Trap

Without the trie, you'd re-explore the board for each word. The trie lets you search all words in one traversal.

← #108