Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#').
You are given a string array sentences and an integer array times both of length n where sentences[i] is a previously typed sentence and times[i] is the corresponding number of times the sentence was typed. For each input character except '#', return the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed.
Here are the specific rules:
3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).3 hot sentences exist, return as many as you can.Implement the AutocompleteSystem class:
AutocompleteSystem(String[] sentences, int[] times) Initializes the object with the sentences and times arrays.List<String> input(char c) This indicates that the user typed the character c.
[] if c == '#' and stores the inputted sentence in the system.3 historical hot sentences that have the same prefix as the part of the sentence already typed. If there are fewer than 3 matches, return them all.
Example 1:
Input
["AutocompleteSystem", "input", "input", "input", "input"]
[[["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]], ["i"], [" "], ["a"], ["#"]]
Output
[null, ["i love you", "island", "i love leetcode"], ["i love you", "i love leetcode"], [], []]
Explanation
AutocompleteSystem obj = new AutocompleteSystem(["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]);
obj.input("i"); // return ["i love you", "island", "i love leetcode"]. There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
obj.input(" "); // return ["i love you", "i love leetcode"]. There are only two sentences that have prefix "i ".
obj.input("a"); // return []. There are no sentences that have prefix "i a".
obj.input("#"); // return []. The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.
Constraints:
n == sentences.lengthn == times.length1 <= n <= 1001 <= sentences[i].length <= 1001 <= times[i] <= 50c is a lowercase English letter, a hash '#', or space ' '.c that end with the character '#'.[1, 200].5000 calls will be made to input.Problem Overview: Design a search autocomplete system that suggests the top 3 historical sentences matching the current prefix as the user types characters. Suggestions are ranked by frequency and then lexicographically when frequencies tie.
Approach 1: Brute Force Prefix Scan + Sorting (Time: O(n log n) per query, Space: O(n))
Store every sentence and its frequency in a hash map. Each time the user types a character, build the current prefix and iterate through all stored sentences to find matches using startswith. Collect matching sentences, then sort them by frequency (descending) and lexicographical order (ascending). Return the top three results. This approach is simple to implement and works for small datasets, but it scales poorly because every keystroke scans the entire sentence list.
Approach 2: Trie with Frequency Map and Heap (Time: O(p + k log m) per query, Space: O(n * L))
Use a Trie to index all sentences by prefix. Each Trie node represents a character and allows fast traversal to the prefix node in O(p) where p is the prefix length. From that node, perform a Depth-First Search to collect candidate sentences stored under that prefix. Use a Heap (Priority Queue) to keep the top 3 sentences ranked by frequency and lexicographical order. This significantly reduces the search space compared to scanning all sentences.
Approach 3: Trie with Cached Top-3 Suggestions (Time: O(p) per query, Space: O(n * L))
An optimized design stores the top three suggestions directly at each Trie node. During insertion or frequency updates, update the node's top-3 list based on frequency and lexicographical ordering. When a user types a character, simply traverse the Trie and return the cached list stored at that node. This removes the need for DFS or heap operations during queries, making lookups extremely fast while slightly increasing update complexity and memory usage.
Recommended for interviews: Interviewers typically expect the Trie-based design. Starting with the brute force solution demonstrates understanding of the ranking rules. The optimized Trie approach shows system design thinking, efficient prefix search, and practical use of data structures for real-time suggestion systems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Scan + Sort | O(n log n) per query | O(n) | Simple implementation when dataset is small |
| Trie + DFS + Heap | O(p + k log m) | O(n * L) | General scalable solution for prefix search with ranking |
| Trie with Cached Top-3 | O(p) | O(n * L) | High-performance autocomplete systems with frequent queries |
LeetCode 642. Design Search Autocomplete System Explanation and Solution • happygirlzt • 17,216 views views
Watch 9 more video solutions →Practice Design Search Autocomplete System with our built-in code editor and test cases.
Practice on FleetCode