944. Sentence Autocomplete

Hard7.5 points estimatedDesignTrieStringSortingHeap4 hints
RPby Rohit Parihar

A search box remembers earlier sentences and how many times each was submitted. Build SentenceAutocomplete; the constructor gets sentences (distinct, lowercase letters and spaces) and times, where times[i] is how often sentences[i] was used.

The user types one character at a time through typeChar(c). A letter or space is appended to the current text, and the method returns up to three remembered sentences that start with the current text, ordered by higher count first, ties by the smaller string in plain ASCII order (a space sorts before letters). The character '#' ends the sentence: it is added to the memory with its count raised by one (or created with count 1), the current text is cleared, and an empty array is returned. '#' is only typed after at least one other character.

Example 1

Input:
operations = ["SentenceAutocomplete","typeChar","typeChar","typeChar","typeChar","typeChar"]arguments = [[["night market","night train","nine lives","neon sign"],[6,6,2,9]],["n"],["i"],["g"],["#"],["n"]]
Output:
[null,["neon sign","night market","night train"],["night market","night train","nine lives"],["night market","night train"],[],["neon sign","night market","night train"]]
Explanation:

Typing n lists the three best of the four sentences (neon sign with 9 uses, then the two 6-use sentences alphabetically). Typing i and g narrows the matches to the night sentences. The # stores nig as a new sentence with count 1, so when n is typed again it is not among the top three.

Example 2

Input:
operations = ["SentenceAutocomplete","typeChar","typeChar","typeChar","typeChar","typeChar"]arguments = [[["red kite","red"],[2,5]],["r"],["e"],["d"],[" "],["k"]]
Output:
[null,["red","red kite"],["red","red kite"],["red","red kite"],["red kite"],["red kite"]]
Explanation:

The sentence red is used more often than red kite, so it comes first; once a space is typed only red kite still matches, and it stays the only match after k.

Constraints

1 ≤ sentences.length ≤ 100; 1 ≤ sentence length ≤ 100; 1 ≤ times[i] ≤ 104

c is a lowercase letter, a space, or '#'

At most 2000 calls to typeChar; typed text is at most 100 characters

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(1) per keystroke, O(L) per committed sentence
Space
O(total characters)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.