Tries: a tree of prefixes
A trie (prefix tree) stores strings one character per level. The root is empty; each edge is a letter; a word is a path from the root, and a node is marked where a word ends. Words that share a prefix share the path: 'car', 'cart' and 'cat' all start with the same c → a.
Looking up a word costs O(length of the word), however many words are stored. More usefully, you can find every word with a given prefix: walk down the prefix, then collect everything below. A hash map can tell you whether 'cat' exists, but not which words start with 'ca' without checking every key.
In real life
Search-box autocomplete, spell checkers, and IP routing tables, where routers find the longest matching address prefix using a trie over bits.
In code: Python · Rust
class Trie:
def __init__(self):
self.root = {}
def add(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True # end-of-word mark
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node: return []
node = node[ch]
out, stack = [], [(node, prefix)]
while stack:
n, s = stack.pop()
if "$" in n: out.append(s)
stack += [(c, s + k) for k, c in n.items() if k != "$"]
return sorted(out)use std::collections::HashMap;
#[derive(Default)]
struct Trie { kids: HashMap<char, Trie>, end: bool }
impl Trie {
fn add(&mut self, w: &str) {
let mut n = self;
for c in w.chars() { n = n.kids.entry(c).or_default(); }
n.end = true;
}
fn has_prefix(&self, p: &str) -> bool {
let mut n = self;
for c in p.chars() {
match n.kids.get(&c) { Some(k) => n = k, None => return false }
}
true
}
}- Each node here is a small map from character to child. For a fixed alphabet, an array of 26 slots is faster but uses more memory.
- The end-of-word mark matters: 'car' is a word, 'ca' is only a prefix.
Check yourself