Word Search II LeetCode 212 — Trie + DFS

LeetCode 212 Word Search II gives you an m x n board of characters and a list of words. Your task is to find all words in the list that can be constructed from letters of sequentially adjacent cells on the board. Two cells are adjacent if they are horizontally or vertically neighboring. The same cell may not be used more than once per word, but different words can reuse cells independently.

The output is a list of all words from the input list that appear on the board. Unlike Word Search I (LeetCode 79), which asks whether a single word exists, Word Search II must handle potentially thousands of words in one pass. This distinction is what makes a naive per-word DFS approach unacceptable and motivates the Trie-based solution.

Understanding the constraints helps appreciate why the naive solution fails and why a Trie is the right data structure. The board can be up to 12x12, words can be up to length 10, and the word list can contain up to 30,000 words. The key insight is that searching each word independently ignores the shared prefixes among words — a waste the Trie eliminates.

The Word Search I solution (LeetCode 79) performs DFS from every cell for a single word: O(m*n * 4^L) where L is the word length. Calling this independently for each word in a list of W words gives O(W * m*n * 4^L) total. On a 12x12 board with 30,000 words of average length 7, this is roughly 30,000 * 144 * 4^7 = 88 billion operations — completely impractical.

The fundamental inefficiency is that each per-word DFS re-traverses the same board cells and ignores shared prefix structure. If the word list contains "apple", "application", and "apply", a per-word approach traverses the "appl" prefix three separate times from every starting cell. A Trie collapses all words with shared prefixes into a single tree, so the DFS follows each prefix path only once regardless of how many words share it.

The per-word approach also cannot prune intelligently: it commits to searching for a specific word and must explore all paths that match its characters, even when many of those paths lead nowhere useful for other words. A Trie-guided DFS prunes the moment no Trie edge matches the current character, regardless of which words are being searched.

A TrieNode has two fields: a children map (dict in Python, HashMap in Java) keyed by character, and an optional word field that stores the complete word string if this node marks the end of a word (or null/None if it does not). Storing the full word string at the terminal node — rather than just a boolean flag — makes it easy to append the word directly to results without reconstructing it during backtracking.

Building the Trie means inserting every word from the input list character by character. For each word, start at the root and walk down the Trie, creating new TrieNode objects for characters that do not yet have a corresponding child. After processing all characters of a word, set the word field of the final node to the word string. Inserting W words of average length L takes O(W * L) time and space.

The Trie structure enables two critical optimizations during DFS: prefix pruning (if no child node exists for the current board character, abandon this path entirely) and word deduplication (once a word is found, set its terminal node's word field to null to prevent it from being collected again if the same path is reached via a different board route).

The main DFS function takes the current board cell (row, col) and the current Trie node. At each step: if the current Trie node has no child for board[row][col], return immediately — this is the key pruning step. Otherwise, descend to the matching child node. If that child node's word field is non-null, a word has been found — add it to results.

To avoid revisiting the same cell within a single word, temporarily mark board[row][col] with a sentinel character like '#' before recursing into the four neighbors. After all recursive calls return, restore the original character. This in-place marking avoids the overhead of a separate visited array and is cache-friendly.

The outer loop calls the DFS function from every cell on the board with the Trie root as the starting node. Words that do not share any prefix with the Trie root's children are pruned on the very first step. Words that share prefixes are explored together along the same DFS paths, paying the traversal cost only once per shared prefix segment.

The most impactful optimization is removing found words from the Trie to prevent duplicate collection. If the board contains two distinct paths that spell "apple", a naive implementation would add "apple" to results twice. Setting the terminal node's word to null after the first collection ensures each word appears in results at most once without needing a separate result-deduplication set.

Pruning empty Trie branches goes further: after the DFS call for a child returns, if the child node now has an empty children map and a null word field, delete the child from the parent's children map. This makes the Trie progressively smaller as words are found. On boards where many words are quickly found in early DFS calls, this can dramatically reduce the work done for later board cells.

Using '#' as a visited marker instead of a separate boolean visited array has two benefits: it avoids allocating an m*n array per DFS call, and it automatically prevents the DFS from following a Trie edge for '#' (since no word in the list contains '#'). Just remember to restore the cell after backtracking.

Python solution: class TrieNode: def __init__(self): self.children={}; self.word=None. def findWords(board, words): root=TrieNode(); [insert(root,w) for w in words]; res=[]; [dfs(board,r,c,root,res) for r in range(len(board)) for c in range(len(board[0]))]; return res. def dfs(board,r,c,node,res): if r<0 or r>=len(board) or c<0 or c>=len(board[0]): return; ch=board[r][c]; if ch=='#' or ch not in node.children: return; nxt=node.children[ch]; if nxt.word: res.append(nxt.word); nxt.word=None; board[r][c]='#'; [dfs(board,r+dr,c+dc,nxt,res) for dr,dc in [(0,1),(0,-1),(1,0),(-1,0)]]; board[r][c]=ch; if not nxt.children: del node.children[ch].

Java solution: class Solution { char[][] board; List<String> res = new ArrayList<>(); public List<String> findWords(char[][] board, String[] words) { this.board=board; TrieNode root=new TrieNode(); for(String w:words) insert(root,w); for(int r=0;r<board.length;r++) for(int c=0;c<board[0].length;c++) dfs(r,c,root); return res; } void dfs(int r,int c,TrieNode node) { if(r<0||r>=board.length||c<0||c>=board[0].length) return; char ch=board[r][c]; if(ch=='#'||!node.children.containsKey(ch)) return; TrieNode nxt=node.children.get(ch); if(nxt.word!=null){res.add(nxt.word);nxt.word=null;} board[r][c]='#'; int[][] dirs={{0,1},{0,-1},{1,0},{-1,0}}; for(int[] d:dirs) dfs(r+d[0],c+d[1],nxt); board[r][c]=ch; if(nxt.children.isEmpty()) node.children.remove(ch); } }

Time complexity: O(m*n * 4^L) in the worst case where L is the maximum word length, but Trie pruning makes the practical performance much faster — especially when the word list is large with many shared prefixes. Space complexity: O(total characters in all words) for the Trie plus O(L) recursion stack depth. Compared to the naive O(W * m*n * 4^L) per-word approach, the Trie solution is dramatically faster on real inputs.

Word Search I (LeetCode 79) is the single-word version of this problem. Solving it first builds the backtracking foundation — the same DFS with visited marking applies directly. The key difference in Word Search II is replacing the character-by-character word matching with Trie edge traversal, which generalizes the single-word DFS to handle multiple words simultaneously without redundant work.

Implement Trie (LeetCode 208) and Design Add and Search Words Data Structure (LeetCode 211) are essential Trie problems. LeetCode 208 builds the core insert and search operations. LeetCode 211 adds wildcard search using '.' to match any character, which requires exploring all children at wildcard positions — a good introduction to Trie-guided DFS before tackling the full board-based backtracking of Word Search II.

Palindrome Pairs (LeetCode 336) is a harder Trie application where you build a Trie of reversed words to efficiently find pairs that form palindromes. It shares the same pattern of encoding a set of strings into a Trie to avoid O(n^2) brute-force comparisons. Together, Word Search II and Palindrome Pairs represent the two main ways Tries accelerate search: prefix-pruned traversal and set-membership with shared-suffix structure.