This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu
Solving Word Search II with Trie and DFS
Finding words in a 2D board may sound like a fun puzzle, but when you scale it to handle large dictionaries and big boards, brute force won’t cut it. In this post, let’s walk through how to efficiently solve Word Search II (a classic LeetCode problem) using Trie + DFS (Depth First Search).
🧩 Problem Statement
We’re given a 2D grid of characters (board) and a list of words (words). The task is to find all the words that can be formed by traversing the grid, where:
- Each letter must be adjacent (up, down, left, right).
- The same cell cannot be used more than once in a word.
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"]
⚡ Approach
A brute force solution would be:
- Try to search every word in the board independently.
- For each word, start a DFS from every cell.
That’s very expensive because for m*n cells and w words, the search would balloon.
Instead, we’ll use a Trie (Prefix Tree):
- Build a Trie with all words in the dictionary.
- This allows us to efficiently prune searches.
- Example: If no word starts with "zx", we don’t waste time exploring it.
- DFS on the Board:
- From each cell, try to explore paths in the Trie.
- If the path matches a word → add to result.
- Mark cells as visited (temporarily replace with
#) to avoid revisiting.
- Collect results in a set (to avoid duplicates) and return.
This drastically improves efficiency because we search once across the board while pruning invalid paths early.
💻 Implementation
Here’s the full working code:
class TrieNode {
constructor() {
this.children = {};
this.wordEnd = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.wordEnd = true;
}
}
var findWords = function (board, words) {
const result = new Set();
const trie = new Trie();
// Step 1: Insert all words into Trie
for (let word of words) {
trie.insert(word);
}
const rows = board.length;
const cols = board[0].length;
// Step 2: DFS with Trie pruning
function dfs(r, c, node, path) {
if (r < 0 || c < 0 || r >= rows || c >= cols) return;
const char = board[r][c];
if (char === "#" || !node.children[char]) return;
node = node.children[char];
path += char;
if (node.wordEnd) {
result.add(path);
}
board[r][c] = "#"; // mark visited
dfs(r + 1, c, node, path);
dfs(r - 1, c, node, path);
dfs(r, c + 1, node, path);
dfs(r, c - 1, node, path);
board[r][c] = char; // backtrack
}
// Step 3: Start DFS from each cell
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dfs(r, c, trie.root, "");
}
}
return Array.from(result);
};
📊 Complexity Analysis
Let:
M = rows,N = cols(board size)W = number of words,L = max word lengthTrie Construction:
O(W * L)(inserting all words)DFS Traversal: Each cell can branch in 4 directions, but pruning ensures we only explore valid prefixes. Worst case is
O(M * N * 4^L), but Trie pruning reduces it drastically.-
Space Complexity:
- Trie takes
O(W * L)space. - DFS recursion stack →
O(L)
- Trie takes
In practice, this performs very efficiently even on large boards and word lists.
🌍 Real-World Scenarios
This problem isn’t just for coding interviews — it shows up in real-world text and pattern searching tasks:
- Word Games: Building AI for Scrabble or Boggle.
- Autocorrect / Autocomplete: Trie + DFS is basically how predictive typing engines explore word completions.
- DNA/Protein Matching: Searching for valid subsequences in a biological sequence grid.
- Crossword Puzzle Generators: Efficiently matching words into constraints.
✨ Key Takeaways
- Trie + DFS = a powerful combo for grid + word search problems.
- Always think about pruning unnecessary searches — that’s where the performance gain lies.
- Problems like this often appear in interviews because they test both data structures and recursion/backtracking skills.
This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu | Sciencx (2025-08-21T13:41:12+00:00) Leetcode – 212. Word Search II. Retrieved from https://www.scien.cx/2025/08/21/leetcode-212-word-search-ii/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.