Preview — Pro guide
You are seeing a portion of this guide. Sign in and upgrade to unlock the full article, quizzes, and interview answers.
Tries (Prefix Trees): Autocomplete, Word Search, and Wildcard Matching
Build production-ready tries for O(L) prefix operations, solve Word Search II with backtracking pruning, and implement wildcard matching. Covers the prefix-count optimization used in autocomplete systems.
When to Use a Trie — Prefix Operations and String Search
A trie (retrieval tree, pronounced 'try') organizes strings by their shared prefixes. Unlike a hash map where each string is a standalone key, a trie shares the common prefix structure — 'car', 'card', and 'care' all share the 'car' prefix nodes.
Use a trie when the operation involves prefixes: autocomplete (find all words starting with a prefix), spell check (find nearest valid words), IP routing (longest prefix match), word game solvers (Boggle, Scrabble), and search bar suggestions.
Don't reach for a trie when: you need exact-match lookups only (hash map is O(1) vs trie's O(L)), or you have a small vocabulary (overhead of trie nodes is not justified). Tries have worse cache performance than hash maps because node traversal jumps through heap memory.
Complexity: insert, search, and startsWith are all O(L) where L is the word length. Hash map search is O(L) average (must hash the entire string) — so trie and hash map have the same time complexity for single-word operations. The trie wins when you need: (1) all words with prefix X — O(L + P) where P = number of matches; (2) counting words with prefix X — O(L) with the count optimization.
Space: O(total characters across all inserted words) in the worst case (no shared prefixes). In practice, shared prefixes can compress storage significantly — a dictionary of 170,000 English words has massive prefix sharing.
How to Decide When a Trie Is the Right Data Structure
Check if the operation involves prefixes
Hash maps give O(1) exact lookup but O(n) prefix queries. If the problem involves 'all words starting with X', 'count words with prefix', or 'autocomplete', a trie is the right choice. For exact-match only, prefer a hash set.
Identify the alphabet and node structure
Lowercase English only: array of 26 is 3-5x faster. Unicode, digits, or mixed: use dict children. Always add is_end: bool to mark valid word boundaries. Add count: int only if prefix-frequency queries are required.
Implement insert first, then build search on top
Insert creates nodes for each character and sets is_end=True at the last character. Search reuses the same traversal but checks is_end at the end. StartsWith is search without the is_end check. Extract the shared traversal into a helper.
For grid word search, combine trie with backtracking
Build a trie from all target words. Run one DFS from every grid cell, simultaneously walking the trie. At each step, check if the current char exists in the trie node's children. If not, prune — no word can start with this path.
Prune after finding each word
After finding a word, set is_end=False and remove leaf nodes that are now empty (no children, not is_end). This prevents finding the same word multiple times and prunes future grid DFS paths that no longer lead to any word.