Word Search II (Trie)
A hard Trie problem included in Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Trie
- Sheets
- 2
- Core for
- 7 roles
- Platform
- LeetCode
The problem
Given a 2D board of characters and a list of words, find all words from the list that can be formed by tracing adjacent cells horizontally or vertically, without reusing a cell within the same word.
Example 1
- 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"]
- Why
- 'oath' is found by tracing o→a→t→h and 'eat' by tracing e→a→t. 'pea' and 'rain' cannot be formed.
Example 2
- Input
- board = [["a","b"],["c","d"]], words = ["abcb"]
- Output
- []
- Why
- 'abcb' requires reusing cell (0,0) after moving to (0,1), which is not allowed.
Constraints
- 1 <= board.length, board[i].length <= 12
- 1 <= words.length <= 3 * 10^4
- words[i] and board[i][j] consist of lowercase English letters
How to think about it
Updated 2026-09-09Searching the grid separately for each word repeats identical board explorations thousands of times. Inverting the perspective by indexing all target words into a single trie lets a single board traversal advance simultaneously along all words that share the current path, pruning invalid prefixes the instant a step leaves the tree.
Approaches, worst first
Individual word search
time O(W * R * C * 3^L) · space O(L)
Run depth-first search on the grid for each word independently. Simple reuse of basic word search, but redundant walks explode when thousands of words share common roots or don't exist on the board.
Trie-guided board DFSWrite this one
time O(R * C * 3^L) · space O(total characters)
Insert all words into a trie. Start DFS from every cell, navigating the trie in lockstep with board neighbors. When reaching a terminal word, collect it and prune leaf nodes on backtracking to avoid duplicate visits.
Where people lose marks · 3
- Returning duplicate words when the same word can be formed along multiple distinct board paths; clearing the word reference in the trie node upon discovery eliminates duplicates.
- Modifying board cells in place to track visited states and forgetting to restore them upon backtracking, permanently corrupting subsequent searches.
- Omitting leaf pruning after matching a word, which causes future board walks to wastefully traverse dead-end branches.
The theory behind it
Trie — the ground this problem stands on. All Trie problems
What Trie is
A trie, also called a prefix tree, is a tree structured for storing words character by character. Instead of storing entire words in individual nodes, each step down a branch represents a single letter. Words that share the same beginning, like car, card, and care, share the exact same starting path down the tree. A special boolean marker sits at the end of each valid word to show that a complete word terminates at that letter.
When to reach for it
Reach for a trie when questions involve prefix lookups, dictionary word searches, autocomplete engines, or matching prefixes against a body of text. Prompts asking whether any word in a dictionary begins with a given prefix, or searching for words on a Boggle board grid, point directly to a trie. It also applies to bitwise tasks, such as finding the maximum XOR pair among integers by treating numbers as binary prefixes.
How the pattern works
Represent each trie node with an array or hash map of child links, plus a boolean flag marking if a complete word ends at that node. When inserting, start at the root and walk down character by character, creating new child nodes whenever a path does not exist yet, then mark the final node as a word ending. When searching, follow the characters; if any child link is missing, the word or prefix does not exist. If all characters match, check the boolean flag to distinguish between a full word and a partial prefix.
What each operation costs
| Operation | Time |
|---|---|
| insert word of length l into trie | O(l) |
| search for full word of length l | O(l) |
| check if any word begins with prefix of length l | O(l) |
What usually goes wrong with Trie
- Confusing prefix matches with full word matches by returning true when characters exist but the end-of-word flag on the final node was never set.
- Allocating fixed 26-slot arrays for child pointers without verifying that all input characters are strictly lowercase English letters.
- Forgetting to prune unvisited branches during board searches, leading to time limit exceeded errors on grids with large word sets.
Which roles need this problem
Trie is a core topic for these 7 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 2 more roles, including Information Retrieval Engineer, Storage Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Trie problems
- Maximum XOR of Two Numbers in ArrayMedium
- Count Distinct Substrings Using TrieMedium
- Longest Word in DictionaryMedium
- Implement Trie II (Count Prefix)Medium
- Number of Distinct Substrings in StringMedium
- Complete StringMedium
- Implement Trie (Prefix Tree)Medium
- Design Add and Search Words Data StructureMedium
Problem set and role mapping as of .