Problem Statement
Word Search II
You are given a grid of letters called the board (m rows by n columns), and a list of words. Your job is to find which of those words can be spelled by walking across the board. A walk moves from a cell to a neighbor that is directly above, below, left, or right of it, and you cannot step on the same cell twice in one word. Return every word from the list that can be spelled this way. The obvious idea is to take each word and search the whole board for it, one word at a time. That is too slow when there are many words. Here is the better idea. Many words share the same starting letters. The word "eat" and the word "ear" both begin with "ea". So instead of searching for each word separately, we load all the words into a structure called a Trie, then walk the board one time and check every word at once. A Trie (say "try") is a tree of letters, like a branching index. Words that share a prefix share the same branch. The big win is this: while walking the board, if the path of letters we have spelled so far is not the start of any word in the Trie, we stop immediately. There is nothing down that road, so we do not waste time on it. That early stopping is called pruning, and it is what makes this fast.
Signals to notice
Brute force first
Run Word Search I for each word independently. Redundant because many words share prefixes. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
The key insight
Build a trie from all words. DFS from each cell, following trie branches. If you reach a trie node marked as a word end, record it. The trie prunes branches that don't match any word prefix. but with massive pruning. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on board=[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words=["oath","pea","eat","rain"]
Build trie: root.children = {o,p,e,r}; leaves store 'oath','pea','eat','rain'. result=[]
Scan (0,0)='o' (in root.children) -> dfs. Path o; visit (0,1)='a' -> oa; (1,1)='t' -> oat; (2,1)='h' -> next.word='oath' => result=['oath'], clear word
Backtrack restores cells; 'oath' branch leaves get pruned from trie (childless)
Scan (1,0)='e' -> dfs e; neighbors (0,0)o,(2,0)i,(1,1)t have no 'a' child -> dead end, no match
Scan (1,3)='e' -> dfs e; visit (1,2)='a' -> ea; (1,1)='t' -> next.word='eat' => result=['oath','eat'], clear word
'pea' and 'rain' never form a path on the board (no 'p', and r-a-i-n not adjacent)
Return result=['oath','eat'] (set {'eat','oath'} matches expected output)What must stay true
The trie lets you check ALL words simultaneously as you explore the grid. If no word in the trie starts with the current path, stop exploring — no word can possibly match. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
build trie from words (each leaf stores its word) for each cell (r,c) whose char is in root.children: dfs(r, c, root) dfs(r, c, node): next = node.children[board[r][c]]; if next.word: record it, clear it mark cell visited; for each in-bounds neighbor with char in next.children: dfs(...) restore cell; if next.children empty: delete this branch (prune)
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not removing found words from the trie — if you don't, you may find the same word multiple times from different starting cells. Decrement the word count or prune the trie branch after finding. The fix is usually to return to the meaning of each move, not just the steps themselves.