Word Search II — Step-by-Step Visualization
hardLeetCode #212ArrayStringBacktrackingTrieMatrix
Given an `m x n` board of characters and a list of strings `words`, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Algorithm Pattern
Backtracking with Trie Pruning
Key Idea
Searching for each word individually on the board using DFS is inefficient (O(W * M * N * 4^L)). Instead, we insert all target `words` into a Trie. Then, we perform a single DFS from every cell on the board. As we traverse the grid, we simultaneously navigate the Trie. If a path on the board doesn't match any prefix in the Trie, we prune the search immediately. This drastically reduces the search space.
Step-by-Step Approach
- Build a Trie from the input `words`.
- For each cell `(r, c)` in the board:
- Start a DFS/backtracking if `board[r][c]` is a child of the Trie root.
- In DFS:
- If the current Trie node is marked as `endOfWord`, add the word to results (and mark it as found to avoid duplicates).
- Mark current cell as visited.
- Explore 4 neighbors if they exist in the current Trie node's children.
- Unmark the current cell (backtrack).
Common Gotchas
- To optimize, remove a word from the Trie once it is found so you don't search for it again.
- Using a simple visited set or temporarily modifying the board character is common for backtracking.