Course4all
Join us on telegram
Home/dsa/Trie/Design Search Autocomplete System

Design Search Autocomplete System

Master this topic with zero to advance depth.

Design Search Autocomplete System

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

Visual Representation

Typed: "i" Prefix "i" matches "i love you" (5), "island" (3), "ironman" (2). Return: ["i love you", "island", "ironman"] Typed: " " (space) Prefix "i " matches "i love you" (5), "i a cool" (2). Return: ["i love you", "i a cool"]
Hard

Examples

Input: ["AutocompleteSystem", "input", "input", "input", "input"] [[["i love you", "island", "ironman", "i love leetcode"], [5, 3, 2, 2]], ["i"], [" "], ["a"], ["#"]]
Output: [null, ["i love you", "island", "i love leetcode"], ["i love you", "i love leetcode"], [], []]
Approach 1

Level I: HashMap (Brute Force Prefix Search)

Intuition

Maintain a HashMap of historical sentences and their counts. For every input, iterate through the entire map, collect sentences starting with the prefix, and sort them to find the top 3. Simple but O(N * L) per query.

⏱ O(N * L) per query.💾 O(N * L)
java
import java.util.*;
class AutocompleteSystem {
    Map<String, Integer> counts = new HashMap<>();
    String prefix = "";
    public AutocompleteSystem(String[] s, int[] t) { for(int i=0; i<s.length; i++) counts.put(s[i], t[i]); }
    public List<String> input(char c) {
        if(c == '#') { counts.put(prefix, counts.getOrDefault(prefix, 0)+1); prefix=""; return new ArrayList<>(); }
        prefix += c; List<String> res = new ArrayList<>();
        for(String s : counts.keySet()) if(s.startsWith(prefix)) res.add(s);
        Collections.sort(res, (a, b) -> counts.get(a).equals(counts.get(b)) ? a.compareTo(b) : counts.get(b)-counts.get(a));
        return res.size() > 3 ? res.subList(0, 3) : res;
    }
}
Approach 2

Level III: Trie + Top-3 Cache

Intuition

Store each historical sentence in a Trie. Each node stores a list of the top 3 hot sentences passing through it. Update these lists incrementally to ensure O(1) query time (just return the list at the current node).

⏱ O(L) per character typed.💾 O(N * L)
java
import java.util.*;
class AutocompleteSystem {
    class Node { Map<String, Integer> counts = new HashMap<>(); List<String> top3 = new ArrayList<>(); Node[] children = new Node[128]; }
    Node root = new Node(), curr = root;
    StringBuilder sb = new StringBuilder();
    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) insert(sentences[i], times[i]);
    }
    private void insert(String s, int k) {
        Node n = root;
        for (char c : s.toCharArray()) {
            if (n.children[c] == null) n.children[c] = new Node();
            n = n.children[c];
            n.counts.put(s, n.counts.getOrDefault(s, 0) + k);
            List<String> list = new ArrayList<>(n.counts.keySet());
            Collections.sort(list, (a, b) -> n.counts.get(a).equals(n.counts.get(b)) ? a.compareTo(b) : n.counts.get(b) - n.counts.get(a));
            if (list.size() > 3) list = list.subList(0, 3);
            n.top3 = list;
        }
    }
    public List<String> input(char c) {
        if (c == '#') { insert(sb.toString(), 1); sb.setLength(0); curr = root; return new ArrayList<>(); }
        sb.append(c);
        if (curr != null) curr = curr.children[c];
        return curr == null ? new ArrayList<>() : curr.top3;
    }
}
← Previous QuestionWord Search II
Next Question →Word Squares