AI Hints
Home›DSA in Python Tutorial›Tries and Tree Review
DSA in Python · Lesson 74 of 132

Practice: Autocomplete

Words with a prefix.

⏱ 2 min read▶ Video at 1:27:06🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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?

Practice: Autocomplete
From the video: Practice: Autocomplete
  • 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.

autocomplete.pypython
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"))
Output
['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.

keyvalue
Walk the prefixO(prefix)
Collect belowevery match
Rankpopularity + heap
Extrastypos, 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
Next up: Trees Quiz — test yourself