LeetCode 642 · Design

Design Search Autocomplete System, explained with a picture

A phone keyboard suggesting words from a letter tree.

Design
▶ Watch it step by step

The problem

Design autocomplete: as the user types, suggest the top 3 past sentences that start with what’s typed, ranked by how often they were used (ties alphabetically).

Input:  cat:5, car:3, cart:2, care:4, dog:1; typed "car"
Output: ["care", "car", "cart"]

Picture it

Picture a phone keyboard storing past words in a letter tree. As you type, it follows the branch for your letters. Every word below that point is a candidate, and the 3 most frequently typed ones are suggested.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Trie + collect words under the prefix node, sorted by (−count, word).

Python solution

class Autocomplete:
    def __init__(self, words, times):
        self.root = {}
        for w, t in zip(words, times):
            node = self.root
            for ch in w:
                node = node.setdefault(ch, {})
            node["#"] = t                     # how often it was typed
    def suggest(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return []
            node = node[ch]
        found = all_words_below(node)
        return sorted(found, key=lambda w: (-times[w], w))[:3]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.