642. Design Search Autocomplete System

Practice Design Search Autocomplete System for free on NudgeCode: Hard, Binary Tree pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Design the autocomplete box of a search engine. The system starts with a history: sentences[i] was typed times[i] times (its hotness). The user then types one character at a time.

• AutocompleteSystem(sentences, times) loads the history.
• input(c):
  • If c is '#', the user finished the current sentence. Add it to the history (hotness + 1, or a new sentence with hotness 1), clear the current input, and return [].
  • Otherwise c is a lowercase letter or a space; append it to the current input and return the top 3 historical sentences that start with the current input, hottest first, ties broken by ASCII order (so " " sorts before letters). Return fewer if fewer match.

Each test is a list of operations and their arguments; the expected output lists what each call returns (null for the constructor).

Example

["AutocompleteSystem","input","input","input","input"]
[[["i love you","island","iroman","i love leetcode"],[5,3,2,2]],["i"],[" "],["a"],["#"]]
->  [null,["i love you","island","i love leetcode"],["i love you","i love leetcode"],[],[]]

After the "#", "i a" is in the history with hotness 1.

Constraints

• 1 <= sentences.length <= 100, 1 <= sentences[i].length <= 100, 1 <= times[i] <= 50
• sentences[i] uses lowercase letters and spaces; c is a lowercase letter, a space or '#'
• Each typed sentence has at most 200 characters; up to 5000 calls to input