Approach
Sorting and greedy selection
For Design Search Autocomplete System, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 57 lines of Python from the credited upstream file 642.py.
- The implementation visibly relies on sequence storage, hash lookup.
- No explicit loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class TrieNode:2 def __init__(self):3 self.children: dict[str, TrieNode] = {}4 self.s: str | None = None5 self.time = 06 self.top3: list[TrieNode] = []7 8 def __lt__(self, other):9 if self.time == other.time:10 return self.s < other.s11 return self.time > other.time12 13 def update(self, node) -> None:14 if node not in self.top3:15 self.top3.append(node)16 self.top3.sort()17 if len(self.top3) > 3:18 self.top3.pop()19 20 21class AutocompleteSystem:22 def __init__(self, sentences: list[str], times: list[int]):23 self.root = TrieNode()24 self.curr = self.root25 self.s: list[str] = []26 27 for sentence, time in zip(sentences, times):28 self._insert(sentence, time)29 30 def input(self, c: str) -> list[str]:31 if c == '#':32 self._insert(''.join(self.s), 1)33 self.curr = self.root34 self.s = []35 return []36 37 self.s.append(c)38 39 if self.curr:40 self.curr = self.curr.children.get(c, None)41 if not self.curr:42 return []43 return [node.s for node in self.curr.top3]44 45 def _insert(self, sentence: str, time: int) -> None:46 node = self.root47 for c in sentence:48 node = node.children.setdefault(c, TrieNode())49 node.s = sentence50 node.time += time51 52 leaf = node53 node: TrieNode = self.root54 for c in sentence:55 node = node.children[c]56 node.update(leaf)57