Tries (prefix trees) and string algorithms appear in autocomplete, spell checking, IP routing, and competitive programming. Mastering trie construction and string pattern matching unlocks a class of problems that hash tables can’t solve efficiently.
Trie Fundamentals
class TrieNode:
def __init__(self):
self.children = {} # char → TrieNode
self.is_end = False
self.count = 0 # words passing through this node
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.count += 1
node.is_end = True
def search(self, word: str) -> bool:
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
return self._find(prefix) is not None
def _find(self, prefix: str) -> TrieNode:
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return nodeComplexity: Insert/Search O(L) time and space, where L = word length. Total space O(ALPHABET_SIZE × N × L).
Pattern 1: Autocomplete / Top K Suggestions
class AutocompleteSystem:
"""LC 642: Design Search Autocomplete System"""
def __init__(self, sentences: list[str], times: list[int]):
self.trie = Trie()
self.freq = defaultdict(int)
for s, t in zip(sentences, times):
self.freq[s] = t
self.trie.insert(s)
self.cur = [] # current input buffer
def input(self, c: str) -> list[str]:
if c == '#':
word = ''.join(self.cur)
self.freq[word] += 1
self.trie.insert(word)
self.cur = []
return []
self.cur.append(c)
prefix = ''.join(self.cur)
# DFS from prefix node to collect all completions
node = self.trie._find(prefix)
if not node:
return []
results = []
def dfs(n, path):
if n.is_end:
results.append((self.freq[path], path))
for ch, child in sorted(n.children.items()):
dfs(child, path + ch)
dfs(node, prefix)
results.sort(key=lambda x: (-x[0], x[1]))
return [r[1] for r in results[:3]]Pattern 2: Word Search II (Trie + DFS)
def findWords(board: list[list[str]], words: list[str]) -> list[str]:
"""LC 212: Find all words on board"""
trie = Trie()
for w in words:
trie.insert(w)
rows, cols = len(board), len(board[0])
result = set()
def dfs(r, c, node, path):
ch = board[r][c]
if ch not in node.children:
return
node = node.children[ch]
path += ch
if node.is_end:
result.add(path)
node.is_end = False # avoid duplicates
board[r][c] = '#' # mark visited
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
dfs(nr, nc, node, path)
board[r][c] = ch # restore
for r in range(rows):
for c in range(cols):
dfs(r, c, trie.root, '')
return list(result)
# Key optimization: prune trie nodes with no remaining words
# (remove leaf nodes after finding a word to avoid redundant DFS)Pattern 3: Replace Words (Trie Prefix Matching)
def replaceWords(dictionary: list[str], sentence: str) -> str:
"""LC 648: Replace words with shortest root"""
trie = Trie()
for root in dictionary:
trie.insert(root)
def replace(word):
node = trie.root
for i, ch in enumerate(word):
if ch not in node.children:
break
node = node.children[ch]
if node.is_end:
return word[:i+1] # return shortest prefix
return word
return ' '.join(replace(w) for w in sentence.split())Pattern 4: Palindrome Pairs
def palindromePairs(words: list[str]) -> list[list[int]]:
"""LC 336: Find all (i,j) where words[i]+words[j] is palindrome
Key insight: insert reversed words into trie; for each word,
check if any reversed word is a prefix/suffix that creates palindrome"""
word_map = {w: i for i, w in enumerate(words)}
result = []
def is_palindrome(s, l, r):
while l < r:
if s[l] != s[r]: return False
l += 1; r -= 1
return True
for i, word in enumerate(words):
n = len(word)
# Case 1: word is prefix of reversed_other
# words[i] + words[j] where words[j] reversed starts with words[i]
for j in range(n + 1):
# Check if word[j:] is palindrome; if word[:j] reversed is in map
if is_palindrome(word, j, n-1):
rev = word[:j][::-1]
if rev in word_map and word_map[rev] != i:
result.append([i, word_map[rev]])
# Check if word[:j] is palindrome; if word[j:] reversed is in map
if j != n and is_palindrome(word, 0, j-1):
rev = word[j:][::-1]
if rev in word_map and word_map[rev] != i:
result.append([word_map[rev], i])
return resultPattern 5: Implement Magic Dictionary (Wildcard)
class MagicDictionary:
"""LC 676: Search with exactly one character changed"""
def buildDict(self, dictionary: list[str]) -> None:
self.words = set(dictionary)
def search(self, searchWord: str) -> bool:
for i in range(len(searchWord)):
for c in 'abcdefghijklmnopqrstuvwxyz':
if c != searchWord[i]:
candidate = searchWord[:i] + c + searchWord[i+1:]
if candidate in self.words:
return True
return False
# Trie variant with wildcard matching:
def search_with_dot(node, word, idx):
"""Search where '.' matches any character (LC 211)"""
if idx == len(word):
return node.is_end
ch = word[idx]
if ch == '.':
return any(search_with_dot(child, word, idx+1)
for child in node.children.values())
if ch not in node.children:
return False
return search_with_dot(node.children[ch], word, idx+1)Pattern 6: Longest Word in Dictionary
def longestWord(words: list[str]) -> str:
"""LC 720: Longest word where every prefix also in words"""
trie = Trie()
for w in sorted(words): # sort for lexicographic preference
trie.insert(w)
result = ''
def dfs(node, path):
nonlocal result
if len(path) > len(result):
result = path
for ch in sorted(node.children):
child = node.children[ch]
if child.is_end: # only traverse valid prefix words
dfs(child, path + ch)
dfs(trie.root, '')
return resultKMP Algorithm: String Pattern Matching
def kmp_search(text: str, pattern: str) -> list[int]:
"""Find all occurrences of pattern in text in O(n+m)"""
def build_lps(p):
"""Longest Proper Prefix which is also Suffix"""
lps = [0] * len(p)
length = 0 # length of previous longest prefix suffix
i = 1
while i < len(p):
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
elif length != 0:
length = lps[length - 1] # don't increment i
else:
lps[i] = 0
i += 1
return lps
lps = build_lps(pattern)
matches = []
i = j = 0 # i = text index, j = pattern index
while i < len(text):
if text[i] == pattern[j]:
i += 1; j += 1
if j == len(pattern):
matches.append(i - j)
j = lps[j - 1]
elif i < len(text) and text[i] != pattern[j]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return matchesRabin-Karp: Rolling Hash
def rabin_karp(text: str, pattern: str) -> list[int]:
"""O(n+m) average, O(nm) worst case"""
n, m = len(text), len(pattern)
BASE, MOD = 31, 10**9 + 9
def hash_str(s, length):
h = 0
for ch in s[:length]:
h = (h * BASE + ord(ch) - ord('a') + 1) % MOD
return h
ph = hash_str(pattern, m)
th = hash_str(text, m)
power = pow(BASE, m - 1, MOD)
matches = []
for i in range(n - m + 1):
if th == ph and text[i:i+m] == pattern: # verify to avoid false positives
matches.append(i)
if i + m < n:
th = (th - (ord(text[i]) - ord('a') + 1) * power) % MOD
th = (th * BASE + ord(text[i+m]) - ord('a') + 1) % MOD
return matchesKey Interview Tips
- Trie vs HashMap: Use trie when prefix queries matter, or when you need ordered traversal of strings. HashMap is faster for exact lookups.
- Memory optimization: Replace dict children with array of size 26 for lowercase-only problems — faster access, predictable memory.
- Trie deletion: Decrement count at each node; remove node if count == 0 and is_end == False — avoids orphaned nodes.
- KMP vs Rabin-Karp: KMP is O(n+m) worst case; Rabin-Karp is O(n+m) average but handles multiple patterns efficiently.
- Aho-Corasick: KMP generalized to multiple patterns — build trie of patterns with failure links; matches all patterns in O(n + m_total + matches).
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use a trie instead of a hash map for string problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use a trie when: (1) you need prefix queries (“does any word start with X?”) u2014 hash maps require iterating all keys; (2) you need ordered traversal of strings (lexicographic order comes for free from trie structure); (3) you’re matching multiple patterns simultaneously (Aho-Corasick builds on trie with failure links); (4) you need to count words sharing a prefix. Use hash maps when you only need exact lookups u2014 they’re O(1) vs trie’s O(L) with better constants. The trie’s overhead is memory: O(ALPHABET u00d7 N u00d7 L) nodes vs O(N) for a hash map.”
}
},
{
“@type”: “Question”,
“name”: “How does the KMP algorithm achieve O(n+m) string matching?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “KMP avoids redundant comparisons by precomputing the Longest Proper Prefix which is also a Suffix (LPS) array for the pattern. When a mismatch occurs at pattern position j, instead of restarting from the beginning, KMP falls back to lps[j-1] u2014 the length of the longest proper prefix of pattern[0..j-1] that matches a suffix. This means the text pointer i never moves backward: each character is examined at most twice (once forward, once when used in a fallback). Building the LPS takes O(m); matching takes O(n). Combined: O(n+m).”
}
},
{
“@type”: “Question”,
“name”: “What is the Aho-Corasick algorithm and when is it used?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Aho-Corasick generalizes KMP to simultaneously match multiple patterns in a single pass over the text. It builds a trie of all patterns, then adds failure links (like KMP’s LPS) between trie nodes u2014 when a character doesn’t match in the current node, follow the failure link to the longest proper suffix that is also a prefix in the trie. Time complexity: O(n + m_total + output) where n is text length, m_total is total pattern length, and output is total number of matches. Used in network intrusion detection (matching thousands of malware signatures), spam filtering, and multi-keyword search u2014 any problem requiring efficient multi-pattern matching.”
}
}
]
}