Practice: Autocomplete
Words with a prefix.
Let's build the autocomplete feature. Given what the user has typed so far, return every word that starts with it. Pause. How would you use the trie?

- Given a prefix
- Return every matching word
- Use the trie
Starts with
First, walk down the trie following the prefix. If a letter is missing, nothing matches. Then, from that node, collect every word below it, with a small recursive generator. Run it. Typing CA gives cap, car, card, and cat. Typing DO gives dog and door.
from trie import Trie
t = Trie()
for w in ["cat", "car", "card", "cap", "dog", "door", "zebra"]:
t.insert(w)
print(t.starts_with("ca"))
print(t.starts_with("do"))
print(t.starts_with("x"))['cap', 'car', 'card', 'cat'] ['dog', 'door'] []
Also uses trie.py
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node:
return []
node = node[ch]
return sorted(self._words(node, prefix))
def _words(self, node, path):
for ch, child in node.items():
if ch == "$": yield path
else: yield from self._words(child, path + ch)Real autocomplete
Real systems add a little more. They store how popular each word is, and return the top few, often using a heap. They handle typos. And they cache common prefixes. But the trie, walking down by letters, is still at the heart of it.
| key | value |
|---|---|
| Walk the prefix | O(prefix) |
| Collect below | every match |
| Rank | popularity + heap |
| Extras | typos, caching |
Summary
Walk down the prefix, then collect every word below. That's autocomplete with a trie. Next, a quiz on trees and heaps.
Key takeaways- Walk the prefix
- Collect the words
- Rank with a heap