Skip to content

642. Design Search Autocomplete System

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#').

You are given a string array sentences and an integer array times both of length n where sentences[i] is a previously typed sentence and times[i] is the corresponding number of times the sentence was typed. For each input character except '#', return the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed.

Here are the specific rules:

  • 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.

Implement the AutocompleteSystem class:

  • 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.

Example 1:

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(["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]);
obj.input("i"); // return ["i love you", "island", "i love leetcode"]. There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
obj.input(" "); // return ["i love you", "i love leetcode"]. There are only two sentences that have prefix "i ".
obj.input("a"); // return []. There are no sentences that have prefix "i a".
obj.input("#"); // return []. The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.

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:

Do this first:

208. Implement Trie (Prefix Tree)

class AutocompleteSystem {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        Map<String, Integer> frequencyMap = new HashMap<>();
        boolean isEnd = false;
    }

    static class Trie {
        TrieNode root;

        Trie() {
            root = new TrieNode();
        }

        public void insert(String sentence, int times) {
            TrieNode cur = root;
            for (char c : sentence.toCharArray()) {
                cur.children.putIfAbsent(c, new TrieNode());
                cur = cur.children.get(c);
                cur.frequencyMap.put(sentence, cur.frequencyMap.getOrDefault(sentence, 0) + times);
            }
            cur.isEnd = true;
        }

        public Map<String, Integer> search(String prefix) {
            TrieNode cur = root;
            for (char c : prefix.toCharArray()) {
                if (!cur.children.containsKey(c)) {
                    return new HashMap<>();
                }
                cur = cur.children.get(c);
            }
            return cur.frequencyMap;
        }
    }

    private final Trie trie;
    private final StringBuilder currentInput; // Stores the characters typed so far for the current input.

    public AutocompleteSystem(String[] sentences, int[] times) {
        trie = new Trie();
        currentInput = new StringBuilder();

        for (int i = 0; i < sentences.length; i++) {
            trie.insert(sentences[i], times[i]);
        }
    }

    public List<String> input(char c) {
        List<String> result = new ArrayList<>();
        if (c == '#') {
            // Finalize the current input
            String sentence = currentInput.toString();
            trie.insert(sentence, 1);
            currentInput.setLength(0);
          // The setLength(0) method clears the StringBuilder, effectively resetting the currentInput to an empty string.
            return result;
        }

        currentInput.append(c);
        String prefix = currentInput.toString();

        // Retrieve all matching sentences and sort them by hotness and lexicographical order
        Map<String, Integer> frequencyMap = trie.search(prefix);
        // PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> (frequencyMap.get(b) - frequencyMap.get(a)));// maxheap

        // 优先队列比较器：按频率降序，频率相同时按字典序升序
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> {
            int freqCompare = frequencyMap.get(b).compareTo(frequencyMap.get(a));
            return freqCompare != 0 ? freqCompare : a.compareTo(b);
        });

        for (String sentence : frequencyMap.keySet()) {
            pq.offer(sentence);
        }


        for (int i = 0; i < 3 && !pq.isEmpty(); i++) {
            result.add(pq.poll());
        }

        return result;
    }
}

/**
 * Your AutocompleteSystem object will be instantiated and called as such:
 * AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
 * List<String> param_1 = obj.input(c);
 */

PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
    @Override
    public int compare(String a, String b) {
        // Compare by frequency in descending order
        int freqCompare = frequencyMap.get(b) - frequencyMap.get(a);

        if (freqCompare != 0) {
            return freqCompare; // If frequencies are different, use frequency comparison
        }

        // If frequencies are the same, compare lexicographically
        return a.compareTo(b);
    }
});

PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> {
    // Compare by frequency in descending order
    int freqCompare = frequencyMap.get(b) - frequencyMap.get(a);
    if (freqCompare != 0) {
        return freqCompare; // If frequencies are different, use frequency comparison
    }
    // If frequencies are the same, compare lexicographically
    return a.compareTo(b);
});

PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> 
    frequencyMap.get(b) - frequencyMap.get(a) != 0 
        ? frequencyMap.get(b) - frequencyMap.get(a) 
        : a.compareTo(b)
);