D
DevExCode

LeetCode 642: Design Search Autocomplete System Solution

Master LeetCode problem 642 (Design Search Autocomplete System), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use a Trie data structure to store the search terms and their frequencies. We can then perform searches starting from the current input prefix and return the top k most frequent search terms that match the prefix.

The steps would be as follows:

  1. Build the Trie data structure to store the search terms along with their frequencies.
  2. Implement a search function that starts from the current input prefix and traverses the Trie to find all matching search terms.
  3. Use a priority queue to keep track of the top k most frequent search terms that match the prefix.
  4. Return the top k search terms with their frequencies.

Time complexity:

  • Building the Trie: O(N * M), where N is the number of search terms and M is the average length of the search terms.
  • Searching for autocomplete suggestions: O(K * M), where K is the number of suggestions to return.
  • Space complexity: O(N * M) for storing the Trie.

Solution Code

class TrieNode {
    Map<Character, TrieNode> children;
    Map<String, Integer> counts;
    
    public TrieNode() {
        children = new HashMap<>();
        counts = new HashMap<>();
    }
}

class AutocompleteSystem {
    TrieNode root;
    String prefix;

    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        prefix = "";
        
        for (int i = 0; i < sentences.length; i++) {
            insert(sentences[i], times[i]);
        }
    }
    
    private void insert(String sentence, int times) {
        TrieNode curr = root;
        
        for (char c : sentence.toCharArray()) {
            TrieNode next = curr.children.get(c);
            if (next == null) {
                next = new TrieNode();
                curr.children.put(c, next);
            }
            curr = next;
            curr.counts.put(sentence, curr.counts.getOrDefault(sentence, 0) + times);
        }
    }
    
    public List<String> input(char c) {
        if (c == '#') {
            insert(prefix, 1);
            prefix = "";
            return new ArrayList<>();
        }
        
        prefix += c;
        TrieNode curr = root;
        
        for (char pc : prefix.toCharArray()) {
            TrieNode next = curr.children.get(pc);
            if (next == null) {
                return new ArrayList<>();
            }
            curr = next;
        }
        
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
            (a, b) -> a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue()
        );
        
        for (Map.Entry<String, Integer> entry : curr.counts.entrySet()) {
            pq.offer(entry);
        }
        
        List<String> result = new ArrayList<>();
        for (int i = 0; i < 3 && !pq.isEmpty(); i++) {
            result.add(pq.poll().getKey());
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 642 (Design Search Autocomplete System)?

This page provides optimized solutions for LeetCode problem 642 (Design Search Autocomplete System) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 642 (Design Search Autocomplete System)?

The time complexity for LeetCode 642 (Design Search Autocomplete System) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 642 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 642 in Java, C++, or Python.

Back to LeetCode Solutions