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
- Insert all historical sentences into a trie, storing the frequency at the end-of-sentence node.
- Keep a pointer to the current trie node as characters arrive, so each
inputcosts only the traversal of the new subtree. - On each
input, collect all sentences under the current node and sort by(-frequency, sentence). - 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 = Noneshort-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.