Design Search Autocomplete System

lcpy gen -n 642   # by problem number
lcpy gen -s design_search_autocomplete_system   # by problem name

​

Problem

• The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
• The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).
• If less than 3 hot sentences exist, return as many as you can.
• When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

• AutocompleteSystem(String[] sentences, int[] times) Initializes the object with the sentences and times arrays.
• List<String> input(char c) This indicates that the user typed the character c.
  • Returns an empty array [] if c == '#' and stores the inputted sentence in the system.
  • Returns the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed. If there are fewer than 3 matches, return them all.

​

Examples

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

Explanation
AutocompleteSystem obj = new AutocompleteSystem([...], [5, 3, 2, 2]);
obj.input("i"); // return ["i love you", "island", "i love leetcode"]
obj.input(" "); // return ["i love you", "i love leetcode"]
obj.input("a"); // return []
obj.input("#"); // return []

​

Constraints

• n == sentences.length
• n == times.length
• 1 <= n <= 100
• 1 <= sentences[i].length <= 100
• 1 <= times[i] <= 50
• c is a lowercase English letter, a hash '#', or space ' '.
• Each tested sentence will be a sequence of characters c that end with the character '#'.
• Each tested sentence will have a length in the range [1, 200].
• The words in each input sentence are separated by single spaces.
• At most 5000 calls will be made to input.

​

Solution

class AutocompleteSystem:
    # Time: input O(n * L + n log n) per call with n = sentence count
    # Space: O(total sentence length)
    def __init__(self, sentences: list[str], times: list[int]) -> None:
        self.counts: dict[str, int] = dict(zip(sentences, times, strict=True))
        self.buffer = ""

    def input(self, c: str) -> list[str]:
        if c == "#":
            if self.buffer:
                self.counts[self.buffer] = self.counts.get(self.buffer, 0) + 1
            self.buffer = ""
            return []
        self.buffer += c
        matches = [s for s in self.counts if s.startswith(self.buffer)]
        matches.sort(key=lambda s: (-self.counts[s], s))
        return matches[:3]

​

Complexity

​

Tags