Trie Summary and Complexity Analysis
mediumTrieSummary
Trie Complexity Profile
| Operation | Time Complexity | Note |
|---|---|---|
| Insertion | $O(L)$ | $L$ = length of the word |
| Search | $O(L)$ | Constant time per character |
| Prefix Query | $O(P + K)$ | $P$ = prefix len, $K$ = number of matches |
| Deletion | $O(L)$ | Requires recursive pruning |
Space Complexity: Worst-case $O(N \cdot L \cdot \Sigma)$, where $N$ is the count of words, $L$ is max word length, and $\Sigma$ is the alphabet size. Tries are memory-intensive but benefit from prefix sharing.
Comparative Analysis: Trie vs. Others
| Use Case | Trie | HashMap | Sorted Array |
|---|---|---|---|
| Exact Match | $O(L)$ | $O(L)$ | $O(L \log N)$ |
| Prefix Search | $O(P)$ | $O(N \cdot L)$ | $O(\log N + K)$ |
| Root Extraction | $O(L)$ | $O(N \cdot L)$ | — |
| Memory Usage | High | Medium | Low |
| Ordering | Sorted Key Order | Unordered | Sorted Range |
Conclusion: Select a Trie when prefix-based operations or root matching are required. For simple equality checks, a Hash Map is generally simpler and more efficient.
Key Usage Categories
1. Prefix Matching
- LC 208: Implement Trie
- LC 211: Design Add and Search Words Data Structure
- LC 648: Replace Words
- LC 1268: Search Suggestions System
2. Word Search (Grid)
- LC 212: Word Search II (Trie + DFS Pruning)
3. Analytics & Autocomplete
- LC 677: Map Sum Pairs
- LC 642: Design Search Autocomplete System
4. Mathematical & Bitwise
- LC 421: Maximum XOR of Two Numbers in an Array
Essential Templates
Standard Array-Based Trie (High Performance)
class StaticTrie {
private static final int MAX_NODES = 100000; // Estimated capacity
private int[][] children = new int[MAX_NODES][26];
private boolean[] isEnd = new boolean[MAX_NODES];
private int nodeCount = 1;
public void insert(String word) {
int u = 0;
for (char c : word.toCharArray()) {
int v = c - 'a';
if (children[u][v] == 0) children[u][v] = nodeCount++;
u = children[u][v];
}
isEnd[u] = true;
}
public boolean search(String word) {
int u = findNode(word);
return u != -1 && isEnd[u];
}
public boolean startsWith(String prefix) {
return findNode(prefix) != -1;
}
private int findNode(String s) {
int u = 0;
for (char c : s.toCharArray()) {
int v = c - 'a';
if (children[u][v] == 0) return -1;
u = children[u][v];
}
return u;
}
}
Engineering Checklist
- Selection Criteria: Use Tries when strings share significant prefixes or when "StartsWith" queries are frequent.
- Node Structure: Use
TrieNode[26]for lowercase English; useMap<Character, TrieNode>for larger charsets (Unicode). - Encapsulation: Does the node need to store full words? Storing the full word string at terminal nodes simplifies DFS/backtracking results.
- Pruning: During
delete, ensure nodes with no other active branches are nullified to reclaim memory. 筋