17. Trie-Based KB Autocomplete

Problem

Fin's help-center search box needs to suggest knowledge-base article titles as the support agent (or customer) types. Rather than scanning every title on each keystroke, build an index once over a fixed set of KB article titles, then answer prefix-autocomplete queries efficiently: given a typed prefix, return every title that starts with it.

Matching is case-sensitive and matches against the full title string, not per-word. Results should come back sorted alphabetically, and an empty list should be returned if nothing matches.

Source: src/17_kb_autocomplete_trie.py

class KBTrie:
    def __init__(self, titles: list[str]): ...
    def autocomplete(self, prefix: str) -> list[str]: ...

>>> trie = KBTrie(["Reset Password", "Reset Email", "Refund Policy", "Cancel Subscription"])
>>> trie.autocomplete("Re")
['Refund Policy', 'Reset Email', 'Reset Password']
>>> trie.autocomplete("Nope")
[]

Step-by-Step Approach

1. Define a trie node with a dict of child nodes keyed by character, plus an optional slot to store the full title when a node marks the end of one.
2. Build the trie once in the constructor: for each title, walk/create a chain of nodes character by character, and stamp the title onto the final node.
3. For autocomplete(prefix), walk the trie one character at a time following prefix. If any character isn't present as a child, no title can match — return [] immediately.
4. If the walk succeeds, you're now standing at the node representing that prefix. Every title stored anywhere in the subtree below (and including) this node is a match.
5. Run a DFS from that node, collecting every non-None title encountered.
6. Sort the collected titles alphabetically before returning.

The key insight is that a trie turns "find everything starting with X" into two separate, cheap steps: an O(len(prefix)) walk to locate the prefix's subtree, then an O(matches) traversal of just that subtree — you never touch titles that don't share the prefix, unlike scanning a flat list.

Reference solution

class _TrieNode:
    def __init__(self):
        self.children: dict[str, "_TrieNode"] = {}
        # set on the node where a full title ends
        self.title: str | None = None


class KBTrie:
    # Build: O(sum of title lengths). Query: O(len(prefix) + matches), via a
    # prefix walk followed by a DFS collect of all titles under that node.
    def __init__(self, titles: list[str]):
        self._root = _TrieNode()
        for title in titles:
            node = self._root
            for ch in title:
                # get-or-create child in one expression
                node = node.children.setdefault(ch, _TrieNode())
            node.title = title

    def autocomplete(self, prefix: str) -> list[str]:
        node = self._root
        for ch in prefix:
            if ch not in node.children:
                # prefix walk: bail out the moment a character is missing
                return []
            node = node.children[ch]
        matches: list[str] = []
        # DFS collect over just the prefix's subtree
        self._collect(node, matches)
        # sort: DFS order depends on dict insertion order
        return sorted(matches)

    def _collect(self, node: _TrieNode, matches: list[str]) -> None:
        # check stored title, not "is this a leaf" (node can have both)
        if node.title is not None:
            matches.append(node.title)
        for child in node.children.values():
            self._collect(child, matches)

Key Functions & Tricks

• dict[str, "_TrieNode"] — child map keyed by character, quoted forward reference
• str | None — PEP 604 union type; None for interior nodes
• Nested-dict trie node pattern — dict key itself is the edge label, no separate edge object
• node.children.setdefault(ch, _TrieNode()) — get-or-create child in one expression
• Check stored title, not "is this a leaf" — a node can have children and a title (shorter title is a prefix of a longer one)
• Prefix walk then DFS collect — walk down to the prefix node, then recurse only that subtree
• node.children.values() — iterate child nodes, discarding character keys
• sorted(matches) — DFS order depends on dict insertion order, so sort guarantees alphabetical output

How to Recognize This Pattern