Tries
15 min
A trie (prefix tree) stores strings character by character down a tree, so that every word sharing a prefix shares the same path from the root. It's the structure behind autocomplete and spell-check.
trie = {}
node = trie
for ch in "cat":
node = node.setdefault(ch, {})
node["#"] = True # marks "this path spells a complete word"
After inserting "cat" and "car", the trie looks like:
{'c': {'a': {'t': {'#': True}, 'r': {'#': True}}}} — the shared "ca"
prefix is stored once.
trie_search fails a prefix that was never marked complete with the # marker, even though every character on the path exists — that's the whole point of the marker.
Compare a trie to a hash set of all words for the query "find every word
starting with pre": a hash set has to check every single entry — O(n).
A trie walks 3 characters down from the root, then reads off every word in
that subtree — the cost depends on the prefix length and result size, not
the total dictionary size. That's the trade a trie makes: slower/bigger
than a hash set for exact single-word lookup in practice, but built for
prefix queries a hash set simply can't do efficiently.
Given the `trie_search` helper below, implement `trie_insert(trie, word)`. `trie` is a nested dict; insert `word` one character at a time, and mark the end of a word with the key `"#"`. Return `trie`.
Given `trie_insert` and `build_trie` below, implement `count_words_with_prefix(trie, prefix)`, returning how many inserted words start with `prefix`.
What's the main advantage of a trie over a hash set for prefix-based lookups (e.g. autocomplete)?
You can build a trie from nested dicts and use it for both exact lookup and prefix-based queries.