183. Design Google Like Search Autocomplete System

Design Search Autocomplete System

Design a SearchAutocomplete system for a search application.

Users type one character at a time to build a sentence. For every typed character except '#', the system must return up to three historical sentences that start with the current typed prefix.

Each historical sentence has a popularity count, which is the number of times that sentence has been completed before.

Suggestions must be sorted by higher popularity first. If two sentences have the same popularity, the sentence with smaller ASCII order must come first.

ASCII order means normal character-by-character order, where the space character comes before lowercase English letters.

When the user types '#', the current sentence is completed and saved into history with its count increased by 1. For '#', return an empty list.

Method Signatures

SearchAutocomplete(List<String> phrases, List<Integer> counts)

Initializes the autocomplete system using historical search sentences.
phrases.get(i) is a sentence that was typed before.
counts.get(i) is the number of times phrases.get(i) was typed before.
All initial phrases are unique.
No parameter value will be null.

List<String> getSuggestions(char ch)

Processes the next character typed by the user.
ch can be a lowercase English letter, a single space character, or '#'.
If ch != '#', append ch to the current input prefix and return up to three matching historical sentences.
If ch == '#' and the current input prefix is not empty, save the current input sentence, increase its historical count by 1, clear the current input prefix, and return an empty list.
If ch == '#' and the current input prefix is empty, do not save anything and return an empty list.

Rules

The popularity of a sentence is the number of times it has been completed before.
Only sentences that start with the current input prefix can be returned.
Return at most three suggestions.
Suggestions are sorted by popularity in descending order.
If two matching sentences have the same popularity, sort them by ASCII order in ascending order.
ASCII order means normal character-by-character order, where the space character comes before lowercase English letters.
If fewer than three matching sentences exist, return all matching sentences.
The character '#' is never part of the stored sentence.

Constraints

1 ≤ phrases.size() ≤ 120
phrases.size() == counts.size()
All initial phrases are unique.
1 ≤ phrases.get(i).length() ≤ 90
1 ≤ counts.get(i) ≤ 10000
Each phrase starts with a lowercase English letter.
Each phrase contains only lowercase English letters and single spaces.
Words inside a phrase are separated by exactly one space.
ch passed to getSuggestions is always a lowercase English letter, a single space character, or '#'.
The total number of stored sentences will not exceed 120.
No parameter value will be null.
Test cases will not pass invalid input values.

Examples

Example 1

SearchAutocomplete autocomplete = new SearchAutocomplete(phrases = List.of("search engine", "search result", "see you", "sea beach"), counts = List.of(5, 3, 4, 2))

autocomplete.getSuggestions(ch = 's')
Output: List.of("search engine", "see you", "search result")
Explanation: All four sentences start with "s". The top three by popularity are "search engine" with count 5, "see you" with count 4, and "search result" with count 3.

Example 2

SearchAutocomplete autocomplete = new SearchAutocomplete(phrases = List.of("search engine", "search result", "see you", "sea beach"), counts = List.of(5, 3, 4, 2))

autocomplete.getSuggestions(ch = 's')
Output: List.of("search engine", "see you", "search result")
autocomplete.getSuggestions(ch = 'e')
Output: List.of("search engine", "see you", "search result")
Explanation: The current prefix is "se". Matching sentences are "search engine", "search result", "see you", and "sea beach". Sorted by popularity, the top three are "search engine" with count 5, "see you" with count 4, and "search result" with count 3.

Example 3

SearchAutocomplete autocomplete = new SearchAutocomplete(phrases = List.of("go home", "good day", "good game"), counts = List.of(2, 5, 5))

autocomplete.getSuggestions(ch = 'g')
Output: List.of("good day", "good game", "go home")
Explanation: "good day" and "good game" both have popularity 5, so ASCII order puts "good day" before "good game". "go home" has lower popularity.

Example 4

SearchAutocomplete autocomplete = new SearchAutocomplete(phrases = List.of("cat", "car", "cart"), counts = List.of(3, 2, 2))

autocomplete.getSuggestions(ch = 'c')
Output: List.of("cat", "car", "cart")
autocomplete.getSuggestions(ch = 'a')
Output: List.of("cat", "car", "cart")
autocomplete.getSuggestions(ch = 'r')
Output: List.of("car", "cart")
autocomplete.getSuggestions(ch = '#')
Output: List.of()
Explanation: The completed sentence "car" is saved again, so its popularity increases by 1. The method returns an empty list for '#'.