LeetCode 212: Word Search II is a Hard trie problem. This Python walkthrough develops a trie-guided board DFS solution, ties every code decision to a concrete invariant, and includes the regression check used before publication.
This independent guide paraphrases the task rather than reproducing LeetCode’s prompt. Use the official page for the exact statement, examples, constraints, and submission runner.
| Difficulty | Hard |
|---|---|
| Topic | Trie |
| Reusable pattern | trie-guided board DFS |
| Complexity | O(mn·4^L) worst-case time with strong trie pruning and O(total word characters) space |
Recognizing the pattern
A trie shares storage and work across common prefixes, allowing a search to abandon an entire family of words after one failed edge.
For this problem specifically, build a trie of target words and DFS from each board cell, pruning paths absent from the trie and removing words after discovery to avoid duplicates. The invariant worth writing beside the code is: Every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.
Step-by-step algorithm
- Identify the input state consumed by
findWords(board, words)and initialize the data required by the trie-guided board DFS pattern. - Build a trie of target words and DFS from each board cell, pruning paths absent from the trie and removing words after discovery to avoid duplicates.
- After each update, verify the page’s central invariant: Every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.
- Finish only after the boundary behavior is covered: The same word should be emitted once; restore board cells after backtracking.
Python solution
class Solution:
def findWords(self, board, words):
root = {}
for word in words:
node = root
for char in word: node = node.setdefault(char, {})
node["$"] = word
rows, cols, answer = len(board), len(board[0]), []
def search(r, c, parent):
char = board[r][c]
if char not in parent: return
node = parent[char]
word = node.pop("$", None)
if word: answer.append(word)
board[r][c] = "#"
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#": search(nr, nc, node)
board[r][c] = char
if not node: parent.pop(char)
for r in range(rows):
for c in range(cols): search(r, c, root)
return answerReading the implementation
The main entry point is findWords(board, words). The named working state includes root, node, rows, char, word; those variables make the trie-guided board DFS state visible instead of hiding it in incidental control flow.
The implementation uses 5 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. In concrete terms, build a trie of target words and DFS from each board cell, pruning paths absent from the trie and removing words after discovery to avoid duplicates.
Correctness argument
Initialization. The data structure starts with exactly the information known before any input element is processed.
Preservation. Build a trie of target words and DFS from each board cell, pruning paths absent from the trie and removing words after discovery to avoid duplicates. Each update records the current item without invalidating earlier decisions; consequently, every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.
Termination. The traversal consumes a finite input or finite state space. At the end, the invariant covers the complete input, which is precisely the condition required for the returned result.
Complexity and trade-offs
O(mn·4^L) worst-case time with strong trie pruning and O(total word characters) space. The auxiliary-space figure excludes the returned output unless the output itself is the structure being built.
A hash set is simpler for exact words, but it cannot answer prefix or wildcard traversal without examining many candidates. That comparison is useful in an interview because it explains why the final implementation is preferable, not merely that it passes.
Regression check
The published implementation belongs to a 100-problem suite that is compiled and exercised behaviorally before deployment.
One reference assertion from that suite is shown below. It targets the normal path while the edge conditions in the next section cover the failure-prone boundaries.
words=Solution().findWords([["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],["oath","pea","eat","rain"]); assert sorted(words)==["eat","oath"]Common mistakes and edge cases
- Problem-specific boundary: The same word should be emitted once; restore board cells after backtracking.
- Pattern-level pitfall: A prefix node is not necessarily a complete word; terminal markers and wildcard branching need separate handling.
- Invariant check: after every update, confirm that every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.
Interview review checklist
- Explain why trie-guided board DFS matches the structure of this input.
- State the invariant in one sentence before tracing code: Every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.
- Derive O(mn·4^L) worst-case time with strong trie pruning and O(total word characters) space from how many times each element or state is visited.
- Test the boundary explicitly: The same word should be emitted once; restore board cells after backtracking.
Browse the searchable 100 LeetCode Python Solutions hub. Previous: 211. Design Add and Search Words Data Structure