⚡Flashcard Drill➔
NeetCode #486LC-642HardTriesNC Algo100
← Back to All Problems

#486 · #642 · Design Search Autocomplete System(设计搜索自动补全系统)

📌 Problem Statement & Constraints

Design a search autocomplete system. AutocompleteSystem(sentences, times) initialises with historical sentences and their frequencies. input(c) consumes one character and returns the top 3 historical sentences starting with the current prefix, ordered by frequency then ASCII order. '#' ends the sentence. Constraints: at most 100 sentences, 10 characters each; at most 5000 calls.

💡 Core Algorithmic Approaches

  1. Insert all historical sentences into a trie, storing the frequency at the end-of-sentence node.
  2. Keep a pointer to the current trie node as characters arrive, so each input costs only the traversal of the new subtree.
  3. On each input, collect all sentences under the current node and sort by (-frequency, sentence).
  4. On '#', increment the frequency of the completed sentence (creating it if new) and reset the state.

💻 Benchmark Python3 Implementation

class AutocompleteSystem:
    def __init__(self, sentences: List[str], times: List[int]):
        self.root = {}
        for s, t in zip(sentences, times):
            node = self.root
            for ch in s:
                node = node.setdefault(ch, {})
            node["#"] = node.get("#", 0) + t   # sentence frequency
        self.cur = ""
        self.node = self.root

    def input(self, c: str) -> List[str]:
        if c == "#":                       # end of sentence
            self.node["#"] = self.node.get("#", 0) + 1
            self.cur = ""
            self.node = self.root
            return []
        self.cur += c
        if self.node is None or c not in self.node:
            self.node = None               # dead end: no completions possible
            return []
        self.node = self.node[c]
        # collect all sentences under the current node
        found = []

        def dfs(node: dict, path: str) -> None:
            if "#" in node:
                found.append((node["#"], path))
            for ch, child in node.items():
                if ch != "#":
                    dfs(child, path + ch)

        dfs(self.node, self.cur)
        found.sort(key=lambda x: (-x[0], x[1]))   # frequency desc, then ASCII
        return [s for _, s in found[:3]]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(P + k log k) per input where P is the number of matching sentences and k is the size of the collected set.
💾 Space Complexity
O(total characters in the history) for the trie.

⚠️ Interview Pitfalls & Follow-ups

  • Re-descending from the root on every input: keeping the node pointer makes each call incremental.
  • Forgetting the dead-end state: once no sentence matches the prefix, later characters cannot revive it, so self.node = None short-circuits.
  • Sorting by frequency alone: ties must be broken by ASCII order of the sentence.
  • Not incrementing the frequency on '#': a completed sentence must be recorded for future suggestions.
  • Excluding the # key from the DFS loop: it is not a character and would corrupt the path.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Tries Problems