Word Search II: Trie + Backtracking on Grid
Insert all target words into a trie and run DFS backtracking on a 2D board to find all valid words simultaneously in O(m × n × 4^L).
Word Search II: Trie + Backtracking on Grid is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Word Search II Problem
Word Search II (LeetCode 212): given an m × n board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (horizontally or vertically), where each cell can only be used once. This is harder than Word Search I (single word) because we need to find all matching words simultaneously — naively running Word Search I for each word is O(W × m × n × 4^L) which is too slow.
Why Trie + Backtracking?
Inserting all target words into a trie and then running DFS backtracking on the board allows us to search for all words simultaneously. At each board cell, instead of checking 'does this path spell my target word?', we check 'does this path match a prefix in the trie?'. As soon as a trie prefix fails, we prune the entire DFS branch — avoiding redundant work across all words sharing that prefix.
Building the Trie from Word List
Insert all words into a trie. Store the complete word at the leaf node (in node.word) rather than just a boolean, so when a complete match is found during backtracking, we can immediately add the word to results without reconstructing it character by character.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')DFS Backtracking on the Grid
Start a DFS from every cell on the board. At each step: (1) check if the current cell's character exists as a child in the current trie node; (2) if yes, mark the cell visited (set it to a sentinel like '#'), recurse into the 4 neighbours; (3) after recursion, restore the cell (unmark). When a trie node has a non-None word, add it to results and set it to None to avoid duplicates.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']Complexity Analysis
Time: O(m × n × 4^L) where L is the maximum word length. For each of the m×n starting cells, the DFS explores up to 4^L paths. The trie prunes paths that don't match any word prefix, so in practice it's much faster. Building the trie is O(W × L) where W is the number of words. Space: O(W × L) for the trie plus O(L) recursion stack depth.
Pruning: Removing Leaf Nodes After Finding
After finding a word, remove the leaf node from the trie (not just null the word) if it has no children. This prevents revisiting dead branches in subsequent DFS calls. When a node's children become empty after finding the word, remove it from its parent's children dict. This optimisation is significant when many words share long prefixes.
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')Why Storing word in Node Is Better
Storing the complete word at the trie leaf node (instead of reconstructing from the DFS path) has two advantages: (1) O(1) word retrieval when a match is found instead of O(L) path reconstruction; (2) setting node.word = None after finding the word is a clean, O(1) deduplication without needing a separate results set. For Word Search II in particular, duplicate prevention is important because the same word could theoretically be found via different paths.
Marking Visited Cells In-Place
Instead of a separate visited set (which would require O(m × n) space per DFS path), we mark cells in-place by replacing their character with a sentinel like '#'. After the DFS returns, restore the original character. This technique: (1) uses O(1) extra space per cell; (2) automatically prevents revisiting within a single path; (3) is completely transparent to the trie traversal since '#' will never be in the trie.
Edge Cases to Handle
Important edge cases: (1) duplicate words in the word list — store in a set, or use the node.word = None trick to prevent duplicates in results; (2) very long words that exceed the board dimensions — they can't be formed, but the DFS naturally handles this by running out of adjacent cells; (3) single-cell board — only single-character words can be found; (4) same word findable via different paths — the node.word = None trick prevents double-counting.
Comparison with Naive Approach
Naive approach: for each of W words, run Word Search I: O(W × m × n × 4^L). With the trie, all words are searched simultaneously: O(m × n × 4^L) regardless of W. For W=1000 words of length 10 on a 10×10 board, naive is 1000× slower than trie. The trie acts as a shared prefix filter that amortises the cost across all words — a classic example of using a data structure to achieve asymptotic improvement.
Full Solution Summary
Complete Word Search II solution: build trie with words, store word string at leaf. For each board cell, run DFS: check if current char exists in current trie node, mark cell as '#', recurse into 4 neighbours, restore cell. When node.word is non-null, add to results and null it. Optionally prune empty trie branches after use. Return the results list. Time: O(m×n×4^L), Space: O(W×L) trie + O(L) recursion.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return resultQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Word Search II uses a trie to enable simultaneous multi-word search with shared prefix pruning, storing the word string in the trie leaf enables O(1) word retrieval and easy deduplication by setting it to None after finding, and in-place visited marking with '#' avoids O(m×n) extra space per DFS path. This completes the Tries and String Algorithms course — you've mastered one of the most powerful string-specific data structures used in interviews.
Frequently asked questions
Is the “Word Search II: Trie + Backtracking on Grid” lesson free?
Yes — the full text of “Word Search II: Trie + Backtracking on Grid” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Word Search II: Trie + Backtracking on Grid”?
Insert all target words into a trie and run DFS backtracking on a 2D board to find all valid words simultaneously in O(m × n × 4^L). You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Word Search II: Trie + Backtracking on Grid” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- TrieNode Class: Insert and Search
- Prefix Search and Starts-With
- Wildcard and Regex Search in a Trie
- Word Search II: Trie + Backtracking on Grid