DSA problem
Design Search Autocomplete System
Design a search-autocomplete system for a search engine. Users type sentences ending with a special character # to signify completion. For each character typed (other than #) the system must return the top-3 historical sentences that share that prefix, ordered by hot-degree (frequency) descending and breaking ties lexicographically. When # is typed the current sentence (built from all characters typed since the last #) is committed with a count increment of one — and the cursor resets so the next character starts a fresh prefix.
The brute-force version scans all historical sentences on every keystroke; with thousands of sentences and dozens of keystrokes per query this quickly becomes too slow. The classic acceleration is a Trie keyed by character, where each Trie node stores a hash map from sentence to its current count for every sentence that passes through this node. This lets us read the top-3 candidates by walking a single edge per keystroke, without rescanning the corpus.
The state we maintain across calls is the current input buffer (a list of characters typed since the last #) and a current Trie cursor that always points to the node corresponding to that prefix. On each non-# character we append it to the buffer and advance the cursor (creating a new child Trie node lazily if no historical sentence used that prefix). Top-3 then becomes: collect the cursor's sentence-to-count map, sort by (-count, sentence), and return the first 3 keys.
On # we commit by walking from the root for each character of the current buffer, ensuring every prefix node's count map records the new sentence with its incremented count. Then we clear the buffer and reset the cursor to the root. The Trie size grows with the total length of all sentences ever entered, but each character of typing remains O(N_branch + N_log) rather than O(corpus).
Examples
AutocompleteSystem(["i love you","island","ironman","i love leetcode"],[5,3,2,2]); input('i')["i love you","island","i love leetcode"]After "i" type " "["i love you","i love leetcode"]Type "a" then "#"[] then []Constraints
- n == sentences.length
- n == times.length
- 1 <= n <= 100
- 1 <= sentences[i].length <= 100
- 1 <= times[i] <= 50
- c is a lowercase English letter, a hash # or space.
- Each tested sentence will be invoked with a series of characters ending with #.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.