The O(n) Club: Word Search II—Why Your Brute Force Solution Needs an Intervention
⚡ TL;DR
Want to find every dictionary word in a letter grid, LeetCode 212-style? You COULD DFS every word (and regret it instantly), or you could build a Trie and let backtracking do the work. Enjoy fewer tears. Example of brute-force pain:
// Don't do this to your CPU: for (String word : words) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (dfs(board, i, j, word, 0)) { result.add(word); } } } } // Welcome to exponential runtime!
🧠 How Devs Usually Mess This Up
Ah, classic panic: “Let’s just DFS every word from every cell. How bad could it be?” Hope you enjoy O(N * m * n * L) performance—because your recruiter won’t. Brute force on a big grid means you’ll see your reflection in a stale coffee cup before seeing an answer.
🔍 What’s Actually Going On
The board is a graph. Each cell is like a little chatty node that can talk (up, down, left, right—no diagonals, we’re not animals) to its neighbors. But words love prefixes and Tries love words. So, build a Trie for all words once, and backtrack across the board—jumping out early if a path isn’t a live prefix in your Trie. Fewer wasted steps, more jaw-dropping runtime.
🛠️ PseudoCode
- Build a Trie from words
insert(word): for each letter, create node if missing; mark word ends.
- Loop through every cell on the board
for each (i, j): backtrack(i, j, rootTrieNode)
- While backtracking:
- If cell is out of bounds or already visited—stop.
- If Trie node has word—add to results, then nuke node.word to avoid repeats.
- Check all 4 directions, keep going if the next letter exists in the Trie path.
- Mark cell as visited (like writing on your hand), then clean up on return.
💻 The Code
// Standard Java magic
class Solution {
static class TrieNode {
TrieNode[] children = new TrieNode[26];
String word;
}
public List
<string> findWords(char[][] board, String[] words) {
List
<string> found = new ArrayList<>();
TrieNode root = buildTrie(words);
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dfs(board, i, j, root, found);
}
}
return found;
}
private void dfs(char[][] board, int i, int j, TrieNode node, List
<string> found) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) return;
char c = board[i][j];
if (c == '#' || node.children[c - 'a'] == null) return;
node = node.children[c - 'a'];
if (node.word != null) {
found.add(node.word);
node.word = null; // No repeats in this club
}
board[i][j] = '#';
dfs(board, i - 1, j, node, found);
dfs(board, i + 1, j, node, found);
dfs(board, i, j - 1, node, found);
dfs(board, i, j + 1, node, found);
board[i][j] = c;
}
private TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode node = root;
for (char c : w.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null)
node.children[idx] = new TrieNode();
node = node.children[idx];
}
node.word = w;
}
return root;
}
}
</string></string></string>
⚠️ Pitfalls, Traps & Runtime Smacks
- Don’t revisit the same cell in one path unless you’re writing an infinite loop demo.
- Null out the Trie node’s word string or your result list will get real spammy, real quick.
- Cloning the board or using a visited[][]? Sure, if you love wasting space. Mutate and un-mutate letters for efficiency (just don’t forget to clean up after).
- Trie + backtracking: Acceptable. Brute force? Grab a pillow, it’s O(N * m * n * L).
🧠 Interviewer Brain-Tattoo
If you’re searching for more than one word, build a Trie—save time, dignity, and potentially a recruiter’s faith in humanity. Remember: “Great devs don’t brute force what a Trie can prune.” (Or: Friends don’t let friends DFS every word.)