Design an autocomplete system that suggests dictionary words based on a typed prefix. The system also records which words are used as complete queries, and future suggestions are ranked by query frequency.
The dictionary is provided once at initialization and remains fixed. Whenever a user finishes typing a whole word (signaled by a special ending character), the system records that word’s query count for ranking purposes.
For maintainability, the implementation must separate the storage layer (Trie) from the orchestration layer. Build a Trie class that handles word insertion and prefix lookup; then build the autocomplete service on top of it.
Implement the Autocompleter class:
Autocompleter(String[] dictionary) – initializes the system with the given distinct lowercase words. All words are unique.List<String> search(String prefix) – returns all dictionary words that start with prefix. The list must be sorted in descending order of how many times each word has been recorded as a completed word, and for words with equal counts, in ascending lexicographical order. If no word matches, return an empty list.void recordEntry(String word) – increments the query count of word by one. The word is guaranteed to be in the original dictionary.Calls to search and recordEntry are interleaved, simulating real user interaction.
Example 1:
Input:
Dictionary = ["apple","apron","apex","banana"]
Operations:
search("ap") -> ["apex","apple","apron"] // all counts 0, lexicographical order
recordEntry("apple")
search("ap") -> ["apple","apex","apron"]
recordEntry("apple")
search("ap") -> ["apple","apex","apron"]
recordEntry("apron")
search("ap") -> ["apple","apron","apex"]
Explanation: initially all frequencies are zero, so words are returned in lexicographical order. After recording "apple" its count becomes 1 and it moves to the front. After a second recording of "apple" it still tops the list. After recording "apron" with count 1, it jumps ahead of "apex" (count 0) but remains behind "apple" (count 2).
Example 2:
Input:
Dictionary = ["cat","car","cart"]
Operations:
search("ca") -> ["car","cart","cat"] // lex order: car, cart, cat
recordEntry("cat")
search("ca") -> ["cat","car","cart"]
Constraints:
1 <= dictionary.length <= 10001 <= dictionary[i].length <= 20'a' to 'z').search and recordEntry calls will not exceed 2000.recordEntry will only be called with words that exist in the initial dictionary.