18. Trie-Based Autocomplete for Voice Commands

Problem

A voice assistant's command palette needs to show live suggestions as a user types a partial command (or as a speech-to-text partial transcript streams in). Build an index once over a fixed catalog of known command phrases, each with a historical usage count, then answer prefix queries efficiently: given a typed prefix, return the top-n matching phrases ranked by usage count (most-used first), ties broken alphabetically.

Matching is case-sensitive on the full phrase string, not per-word.

Source: src/18_voice_command_autocomplete.py

class VoiceCommandIndex:
    def __init__(self, phrases: list[tuple[str, int]]): ...
    def autocomplete(self, prefix: str, top_n: int) -> list[str]: ...

>>> idx = VoiceCommandIndex([("set a timer", 42), ("set an alarm", 17), ("stop playback", 30)])
>>> idx.autocomplete("set", top_n=2)
['set a timer', 'set an alarm']
>>> idx.autocomplete("stop", top_n=5)
['stop playback']

Step-by-Step Approach

1. Build a trie over the phrase catalog once, at construction time: for each phrase, walk/create a child node per character, and at the terminal node store the full phrase string and its usage count.
2. To answer autocomplete(prefix, top_n), first walk from the root one character at a time following prefix. If any character has no matching child, nothing in the catalog has that prefix — return an empty list immediately.
3. If the walk completes, the node it lands on represents "every phrase that starts with prefix" as its entire subtree.
4. Recursively collect every terminal (phrase, count) pair in that subtree — a node has a phrase exactly when it was marked as terminal during construction, regardless of whether it also has children (one phrase can be a prefix of another).
5. Sort the collected matches by usage count descending, breaking ties alphabetically by phrase.
6. Return only the first top_n phrases from that sorted list.

The key insight is splitting the work into two phases with different costs: the trie walk to the prefix node is O(len(prefix)), independent of catalog size, while the ranking step is O(m log m) where m is only the number of matches under that prefix — you never touch phrases that don't share the prefix at all, which is what makes a trie faster than scanning every phrase and checking str.startswith.

Reference solution

class _Node:
    __slots__ = ("children", "phrase", "count")

    def __init__(self):
        self.children: dict[str, "_Node"] = {}
        self.phrase: str | None = None  # set only at a node that terminates a phrase
        self.count: int = 0


class VoiceCommandIndex:
    def __init__(self, phrases: list[tuple[str, int]]):
        self.root = _Node()
        for phrase, count in phrases:
            node = self.root
            for ch in phrase:
                node = node.children.setdefault(ch, _Node())
            node.phrase = phrase
            node.count = count

    def _collect(self, node: _Node, out: list[tuple[str, int]]) -> None:
        if node.phrase is not None:
            out.append((node.phrase, node.count))
        for ch in sorted(node.children):
            self._collect(node.children[ch], out)

    def autocomplete(self, prefix: str, top_n: int) -> list[str]:
        # walk down to the node representing `prefix`; if the path breaks,
        # nothing in the trie has this prefix
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]

        matches: list[tuple[str, int]] = []
        self._collect(node, matches)
        # rank by usage descending, ties broken alphabetically
        matches.sort(key=lambda pc: (-pc[1], pc[0]))
        return [phrase for phrase, _ in matches[:top_n]]

Key Functions & Tricks

• dict.setdefault(ch, _Node()) — creates a child node on first visit and reuses it on subsequent phrases sharing that prefix, in one line.
• __slots__ on _Node — keeps per-node memory overhead low, which matters when the trie has one node per distinct character position across the whole catalog.
• node.phrase is not None — the terminal marker; checking for None rather than a boolean flag also lets a terminal node store the phrase string directly.
• Prefix walk that early-returns [] — avoids any subtree traversal at all when the prefix doesn't exist in the catalog.
• matches.sort(key=lambda pc: (-pc[1], pc[0])) — negating the count sorts descending by frequency while sorting ascending alphabetically for ties, in a single sort call.
• matches[:top_n] — slicing is safe even when fewer than top_n matches exist; Python slices never raise on an out-of-range end index.

How to Recognize This Pattern