Tries
A trie (prefix tree) is a tree-like data structure that stores strings character by character, where each node represents a prefix. Tries enable O(L) lookup, insertion, and prefix search where L is the string length — independent of how many strings are stored. They are the optimal choice for autocomplete, spell-checking, and prefix-matching problems.
When to Use
- →You need to search for words or prefixes efficiently
- →You need to implement autocomplete or word suggestion
- →You need to find all words matching a pattern with wildcards
- →You need to search a grid for words from a dictionary (word search)
Approach
A trie node contains a map of children (one per possible character) and a boolean flag indicating whether it marks the end of a complete word. To insert a word, traverse from the root, creating child nodes as needed, and mark the last node as a word end.
To search for a word, follow the character path from the root. If you reach a dead end (no child for the next character), the word doesn't exist. To search for a prefix, do the same but don't require the end-of-word flag.
For word search problems on grids, combine trie traversal with DFS/backtracking. Insert all dictionary words into a trie, then start DFS from each grid cell. At each step, check if the current path exists as a trie prefix — if not, prune that branch. This avoids checking words that can't possibly be formed from the current position.
Code Template
class TrieNode {
constructor() {
this.children = {};
this.isEnd = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEnd = true;
}
search(word) {
const node = this._findNode(word);
return node !== null && node.isEnd;
}
startsWith(prefix) {
return this._findNode(prefix) !== null;
}
_findNode(s) {
let node = this.root;
for (const char of s) {
if (!node.children[char]) return null;
node = node.children[char];
}
return node;
}
}