Design Search Autocomplete System

This page explains Java solution to problem Design Search Autocomplete System using Trie data structure.

Problem Statement

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:

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

Your job is to implement the following functions:

DesignSearchAutocompleteSystem(String[] sentences, int[] times): This is the constructor. The input is historical data. Sentences is a string array consists of previously typed sentences. Times is the corresponding times a sentence has been typed. Your system should record these historical data.

Now, the user wants to input a new sentence. The following function will provide the next character the user types:

List input(char c): The input c is the next character typed by the user. The character will only be lower-case letters ('a' to 'z'), blank space (' ') or a special character ('#'). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.

Example 1:

Operation: DesignSearchAutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
"i love you" : 5 times
"island" : 3 times
"ironman" : 2 times
"i love leetcode" : 2 times
Now, the user begins another search:

Operation: input('i')
Output: ["i love you", "island","i love leetcode"]
Explanation:
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.

Operation: input(' ')
Output: ["i love you","i love leetcode"]
Explanation:
There are only two sentences that have prefix "i ".

Operation: input('a')
Output: []
Explanation:
There are no sentences that have prefix "i a".

Operation: input('#')
Output: []
Explanation:
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.

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class DesignSearchAutocompleteSystem {

    static class Node {
        HashMap<Character, Node> map;
        int times = 0;

        Node(int times) {
            this.times = times;
            map = new HashMap<Character, Node>();
        }
    }

    static class Entry {
        String str;
        int times;

        Entry(String str, int times) {
            this.str = str;
            this.times = times;
        }
    }

    static class Trie {
        Node root = new Node(0);

        private void addWord(String word, int times) {
            Node current = root;
            for(int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if(!current.map.containsKey(ch)) {
                    current.map.put(ch, new Node(0));
                }
                current = current.map.get(ch);
            }
            current.times += times;
        }

        private List<Entry> search(String prefix) {
            Node current = root;
            for(int i = 0; i < prefix.length(); i++) {
                char ch = prefix.charAt(i);
                if(current == null) return new ArrayList<Entry>();
                else if(current.map.containsKey(ch)) {
                    current = current.map.get(ch);
                }
                else {
                    return new ArrayList<Entry>();
                }
            }
            List<Entry> res = getAll(prefix, current);
            return res;
        }

        private List<Entry> getAll(String str, Node current) {
            List<Entry> res = new ArrayList<Entry>();
            if(current.times > 0) {
                res.add(new Entry(str, current.times));
            }
            for(Map.Entry<Character, Node> node: current.map.entrySet()) {
                res.addAll(getAll(str + node.getKey(), node.getValue()));
            }
            return res;
        }
    }

    Trie trie = new Trie();
    public DesignSearchAutocompleteSystem(String[] sentences, int[] times) {
        for(int i = 0; i < times.length; i++) {
            trie.addWord(sentences[i], times[i]);
        }
    }

    String prefix = "";
    public List<String> input(char c) {
        if(c == '#') {
            //System.out.println("Adding word: "+prefix);
            trie.addWord(prefix, 1);
            prefix = "";
            return new ArrayList<String>();
        }
        else {
            prefix += c;
            List<Entry> list = trie.search(prefix);
            return reformat(list);
        }
    }

    private List<String> reformat(List<Entry> list) {
        List<String> res = new ArrayList<String>();
        Collections.sort(list, new Comparator<Entry>(){
            public int compare(Entry n1, Entry n2) {
                int cmp = Integer.valueOf(n2.times).compareTo(n1.times);
                if(cmp == 0) return n1.str.compareTo(n2.str);
                return cmp;
            }
        });
        for(int i = 0; i < Math.min(3, list.size()); i++) res.add(list.get(i).str);
        return res;
    }
}

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

Time Complexity

DesignSearchAutocompleteSystem() takes O(K * L) < br/> input() takes O(P + Q + M * log M)
Where K is avg length of each sentences
L is total number of sentences P is length of sentence formed
Q is length of nodes in trie after sentence
M is result that we need to sort

Space Complexity

O(C) Where
Q is total number of characters in all the sentences in an input array