Word Search II

Given an m x n board of letters and a list of words, return all words that can be formed by sequentially adjacent letters (up/down/left/right). A letter cell may be used at most once per word.

Function signature

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

Inputs / outputs

• board: grid of lowercase letters.
• words: list of words.
• Return: all words found (order does not matter).

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
• 1 <= len(words) <= 30_000

Core idea (near-solution)

Use a trie for the word list. Then DFS from each cell, following trie edges. This prunes paths that cannot match any word.

Invariant: the current DFS path corresponds to a prefix in the trie; if no child exists, stop.

Algorithm (step-by-step)

1. Build a trie of all words; store full word at terminal nodes.
2. For each cell, DFS while following trie children.
3. When you reach a trie node with a word, add it to results and clear it to avoid duplicates.
4. Mark cells as visited during DFS and restore afterward.

Correctness sketch

• Invariant: the current DFS path corresponds to a prefix in the trie; if no child exists, stop.
• Each node represents a prefix; inserting builds all prefixes for a word.
• Searching follows the unique path for the word/prefix.
• Wildcards branch over all possible children, covering all matches.

Trace (hand walkthrough)

Example input:
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"]

Walk:
- find "oath": o(0,0)->a(0,1)->t(1,1)->h(2,1)
- find "eat": e(1,3)->a(1,2)->t(1,1)
- "pea" and "rain" not found -> output ["oath","eat"]

Pitfalls to avoid

• Not pruning when the trie has no matching child.
• Returning duplicate words (clear isWord after found).

Complexity

• Time: O(m*n*4^L) in worst case, but heavily pruned by the trie.
• Extra space: O(total word length) for trie and recursion stack.

Implementation notes (Go)

• Use a trie to prune search when no prefix exists.
• Mark found words to avoid duplicates, and restore board cells on backtrack.