Word Search II

Given a board of letters and a list of words, return all words that can be formed by walking adjacent cells horizontally or vertically. A cell may not be reused within the same word.

Why this is worth learning

Combine two pruning rules: a board path cannot reuse cells, and its letters must remain a dictionary prefix. The trie shares work among words; it does not replace the board visited state.

Before coding: one-minute experiment

With dictionary ["a","ab"] and adjacent board cells a,b, why may you clear the terminal word at a but not delete the entire a branch?

Function signature

func FindWords(board [][]byte, words []string) []string

Inputs / outputs

• board: m x n grid of lowercase letters.
• words: target words.
• Return: all target words present in the board, in any order.

Example

board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath", "pea", "eat", "rain"]
Output: ["oath", "eat"]

Constraints

• 1 <= m, n <= 12
• Words contain lowercase English letters.

Core idea (near-solution)

Searching the board independently for every dictionary word repeats many shared prefixes. Build their trie and explore a board path only while it spells a dictionary prefix. The trie state alone is insufficient: legal continuations also depend on which cells the current path has used. Mark a cell before exploring and restore it afterward so other paths can reuse it. Recording a terminal word must not end the branch, since a longer word may share that prefix. Clearing only the stored terminal word prevents duplicate output without deleting longer candidates.

Invariant: On entry to dfs(r,c,node), node represents the prefix before the current cell; after following its matching child and marking the cell, the trie node represents the extended path and the marks are exactly its used cells.

Algorithm (step-by-step)

1. Insert all words into a trie, storing the full word at terminal nodes.
2. Start DFS from each cell.
3. If the current character has no trie child, stop.
4. Move into the child. If it stores a word, add the word to results and clear it to avoid duplicates.
5. Temporarily mark the board cell visited.
6. Explore four neighbors.
7. Restore the board cell before returning.

Correctness sketch

At each DFS entry, the trie node represents the letters chosen before the current cell and the temporary board marks represent exactly the cells on that current path. Following the cell letter succeeds only for a dictionary prefix. Marking the cell before recursion prevents reuse; restoring it afterward makes it available to different paths and different starting cells. Reaching a terminal proves one dictionary word is formed by a legal path. Clearing only its stored word suppresses duplicate output while retaining children needed for longer words. Every legal matching path is explored until its terminal, so all distinct present words are returned.

Trace (hand walkthrough)

Start at o -> prefix o exists.
Move to a -> prefix oa exists.
Move to t -> prefix oat exists.
Move to h -> terminal oath, record it.
A branch like o -> e stops if oe is not a trie prefix.

Pitfalls to avoid

• Reusing the same board cell in one word.
• Returning duplicate words when the same word is found by multiple paths.
• Continuing DFS after the current prefix is already impossible.

Debugging lens

Test shared prefixes, a word found by several paths, and a tempting path that reuses one cell. Compare answers as a set while rejecting duplicate returned words. Verify the board is restored after the call.

Complexity

Let D be total dictionary characters and L the longest nonempty word. Trie construction takes O(D) time and space. A loose search upper bound is O(m n 4 * 3^(L-1)), reduced by trie pruning and the limit of m n distinct cells per path. Include O(D) construction in the total time; recursion depth is O(min(L,m n)), plus returned strings.

Implementation notes (Go)

• Store word string at terminal nodes; clearing it after recording avoids a result set.
• Mark visited by temporarily replacing the board byte with '#' and restoring it.

Contract precision

The board is nonempty and rectangular; dictionary words are nonempty lowercase English strings. The result contains each found word once in any order. The reference restores all temporary board marks before returning.

Reconstruction checkpoint

On a one-row board [a,b,a] with words ["a","ab","aba","abaa"], give the distinct outputs. Explain separately why a prefix terminal cannot stop exploration and why abaa is invalid.

Return to Trie · Module quiz