Trie Recap and When to Use
A Trie (prefix tree) stores strings character by character. Insert and search are both O(L) per word where L = word length. The key advantage over a hash set: the trie supports prefix operations efficiently — find all words with a given prefix, count words with a prefix, or prune DFS early when no words match. Use a Trie when: the problem involves prefix matching, autocomplete, or searching for words with a shared structure. Often a better fit than sorting + binary search when multiple prefix queries are needed.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
self.word = None # store word at end node for easy retrieval
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
node.word = word
def search(self, word) -> bool:
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_endPattern 1: Word Search II (LC 212)
Find all words from a dictionary that exist in a 2D character grid. Naive approach: for each word, DFS in the grid — O(words * 4^L). With a Trie: build a trie of all dictionary words. DFS on the grid; at each cell, check if the current path is a trie prefix. If not: prune the DFS immediately. If the node is a word end: record the found word. This finds all words in one DFS pass — O(4^L) for DFS instead of O(words * 4^L). Optimization: mark a trie node as already-found after it’s added to results (delete from trie or set a flag) — avoids re-adding the same word if it appears multiple times in the grid. Mark cells as visited during DFS (set to ‘#’, restore after backtrack).
def find_words(board, words):
trie = Trie()
for w in words: trie.insert(w)
m, n = len(board), len(board[0])
result = []
def dfs(node, r, c):
char = board[r][c]
if char not in node.children: return
next_node = node.children[char]
if next_node.word:
result.append(next_node.word)
next_node.word = None # deduplicate
board[r][c] = '#' # mark visited
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != '#':
dfs(next_node, nr, nc)
board[r][c] = char # restore
for r in range(m):
for c in range(n):
dfs(trie.root, r, c)
return resultPattern 2: Palindrome Pairs (LC 336)
Find all pairs (i, j) where words[i] + words[j] is a palindrome. Brute force: O(n^2 * L). Trie approach: insert all reversed words into a trie. For each word W: traverse the trie with W’s characters. At each trie node encountered: if the remaining suffix of W (from the current trie position) is a palindrome AND the trie path ends a word: found a pair. Also check the full reversal: if W exactly matches a reversed word (not itself): that’s a pair. O(n * L^2) — much better than O(n^2 * L). The palindrome check at each node is the key: it means the word from the trie + the palindromic suffix of W + the trie word form a complete palindrome. This pattern requires careful index tracking — easier to implement with a hash map (store {word: index}) than a Trie in practice.
Pattern 3: Replace Words (LC 648)
Replace words in a sentence with their shortest root from a dictionary. Build a trie from the dictionary. For each word in the sentence: traverse the trie character by character. The first time we hit an is_end node: replace the word with the root (the path taken so far). If no root found: keep the original word. O(n * L) where n = sentence words, L = max word length. This is the canonical “find the shortest prefix that exists in a set” operation — O(L) per word with a trie vs O(L^2) with a hash set (checking each prefix one by one).
Pattern 4: Map Sum Pairs (LC 677) and Prefix Count
Insert key-value pairs into a trie. Query: sum of values of all keys with a given prefix. Augment each trie node with a sum (total value of all words in its subtree). On insert: update sum for every node on the path (not just the leaf). On prefix query: traverse to the prefix node, return its sum. O(L) per operation. Similar pattern: count words with prefix — store count instead of sum. This generalized “aggregate over subtree” pattern is powerful: precompute any aggregate at each node and keep it updated on insert/delete.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide