Problem · String
Autocomplete System
Learn this problem● Hard
PinterestFULLTIMEONSITE INTERVIEW
PinterestFULLTIMEONSITE INTERVIEWProblem statement
Implement a finite operation-sequence adapter for a sentence autocomplete system.
The system starts with parallel arrays sentences and times, where times[i] is the historical frequency of sentences[i]. Process the characters in inputs from left to right while maintaining one current query.
- For a lowercase letter or space, append it to the current query and return up to three stored sentences that start with that query.
- Rank matches by frequency in descending order, then by ascending lexicographic order when frequencies tie.
- For
#, record the current nonempty query as a sentence with its frequency increased by one, reset the current query to empty, and return an empty list for that operation.
Return one suggestion list for every character in inputs, including an empty list for each # operation.
Function
autocomplete(sentences: String[], times: int[], inputs: String) → String[][]Examples
Example 1
sentences = ["i love you","island","iroman","i love leetcode"]times = [5,3,2,2]inputs = "i a#i "return = [["i love you","island","i love leetcode"],["i love you","i love leetcode"],[],[],["i love you","island","i love leetcode"],["i love you","i love leetcode","i a"]]The first four operations type and commit i a, giving it frequency 1. The final two operations begin a new query, so i a appears as the third suggestion after the prefix i .
Example 2
sentences = ["abc","abb","abd"]times = [2,2,2]inputs = "ab#"return = [["abb","abc","abd"],["abb","abc","abd"],[]]All three stored matches have the same frequency, so lexicographic order decides their ranking. The final operation records ab and resets the query.
Constraints
1 <= sentences.length == times.length <= 1001 <= sentences[i].length <= 1001 <= times[i] <= 10^4- Initial sentences are unique and contain only lowercase English letters and spaces.
1 <= inputs.length <= 1000- Every character in
inputsis a lowercase English letter, a space, or#. - Each
#appears only when the current query is nonempty.