Design Search Autocomplete System

Hard Tries Basics Original on LeetCode

Design Search Autocomplete System is a hard tries problem solved with the basics pattern. The best approach, optimal (trie with a top-3 list per node), runs in O(L) per add, O(1) per character typed time and O(T) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan every sentence) up.

Problem

Build the suggestion box of a search bar. It starts with a history of past searches: sentences[i] was searched times[i] times. Then the user types one character at a time through input(c).

  • If c is a letter or a space, it extends the sentence being typed. Return the three most popular past sentences that start with everything typed so far, most searched first; sentences with the same count are ordered alphabetically (character codes, so a space comes before any letter). Return fewer if fewer match.
  • If c is '#', the user has finished the current sentence: record it as searched one more time (adding it to the history if it is new), start a fresh sentence, and return an empty list.

Implement the class AutocompleteSystem with the constructor AutocompleteSystem(String[] sentences, int[] times) and the method List<String> input(char c).

Examples

Example 1

Input
AutocompleteSystem(["code red", "coffee", "cold", "cola", "comet"], [3, 5, 2, 2, 1]); input('c'); input('o'); input('l'); input('d'); input('#'); input('c')
Output
["coffee", "code red", "cola"], ["coffee", "code red", "cola"], ["cola", "cold"], ["cold"], [], ["coffee", "code red", "cold"]
Why
cola and cold are tied at 2, so cola wins alphabetically. Pressing # saves cold as searched once more, raising it to 3, which ties code red; code red sorts first.

Example 2

Input
AutocompleteSystem(["go home", "go"], [1, 1]); input('g'); input('o'); input(' '); input('x'); input('#'); input('g')
Output
["go", "go home"], ["go", "go home"], ["go home"], [], [], ["go", "go home", "go x"]
Why
Spaces are part of the prefix. go x matches nothing while typed, but after # it is a new sentence with count 1.

Constraints

  • 1 <= sentences.length <= 100, sentences.length == times.length, 1 <= times[i] <= 50.
  • 1 <= sentences[i].length <= 100; sentences use lowercase English letters and spaces, and are distinct.
  • c is a lowercase letter, a space ' ', or '#'; '#' is never the first character of a sentence being typed.
  • Each typed sentence has at most 200 characters, and there are at most 5000 calls to input.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan every sentence)O(N · L + N log N) per callO(N · L)
Optimal (trie with a top-3 list per node)O(L) per add, O(1) per character typedO(T)

1Brute force (scan every sentence)

TimeO(N · L + N log N) per callEach call checks all N stored sentences (prefix check up to L characters) and sorts the matches.
SpaceO(N · L)The map stores every sentence.

Store counts in a hash map and the typed text in a builder. On each character, scan every stored sentence, keep those that start with the typed text, sort them by count (high first) then alphabetically, and return the first three. On #, add 1 to the typed sentence's count and reset.

  1. Constructor: count[sentences[i]] += times[i].
  2. input('#'): count[typed] += 1, clear typed, return [].
  3. Otherwise append c to typed, collect sentences with prefix typed, sort by (-count, sentence), return the first three.
class AutocompleteSystem {
    private final Map<String, Integer> count = new HashMap<>();
    private final StringBuilder typed = new StringBuilder();

    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) count.merge(sentences[i], times[i], Integer::sum);
    }

    public List<String> input(char c) {
        if (c == '#') {
            count.merge(typed.toString(), 1, Integer::sum);
            typed.setLength(0);
            return new ArrayList<>();
        }
        typed.append(c);
        String prefix = typed.toString();
        List<String> matches = new ArrayList<>();
        for (String s : count.keySet())
            if (s.startsWith(prefix)) matches.add(s);
        matches.sort((a, b) -> {
            int ca = count.get(a), cb = count.get(b);
            return ca != cb ? cb - ca : a.compareTo(b);
        });
        return new ArrayList<>(matches.subList(0, Math.min(3, matches.size())));
    }
}

2Optimal (trie with a top-3 list per node)

TimeO(L) per add, O(1) per character typedA sentence update touches L nodes and sorts a list of at most four at each; a query moves one step and copies at most three strings.
SpaceO(T)T = total characters stored in the trie; each node also holds up to three references.

Build a trie over the sentences. Every node keeps the (at most) three best sentences that pass through it. When a sentence's count grows, walk its path and, at each node, put the sentence in that node's list if it is missing, re-sort the short list and cut it back to three. Because counts only grow, a sentence can only enter a node's top three at the moment its own count changes, so these lists stay correct. Queries keep a pointer to the node of the current prefix and just read its list.

  1. add(s, k): count[s] += k; walk s through the trie creating nodes; at each node, add s to node.top if absent, sort by (-count, sentence), drop anything past the third.
  2. Constructor: add(sentences[i], times[i]).
  3. input(c): on '#', add(typed, 1), clear typed, reset the pointer to the root and return [].
  4. Otherwise append c; move the pointer to its child for c (null stays null once a prefix has no matches); return a copy of pointer.top, or [] for null.
class AutocompleteSystem {
    private static class Node {
        Node[] next = new Node[27];
        List<String> top = new ArrayList<>();
    }

    private final Node root = new Node();
    private final Map<String, Integer> count = new HashMap<>();
    private final StringBuilder typed = new StringBuilder();
    private Node cur = root;

    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) add(sentences[i], times[i]);
    }

    public List<String> input(char c) {
        if (c == '#') {
            add(typed.toString(), 1);
            typed.setLength(0);
            cur = root;
            return new ArrayList<>();
        }
        typed.append(c);
        if (cur != null) cur = cur.next[index(c)];
        return cur == null ? new ArrayList<>() : new ArrayList<>(cur.top);
    }

    private int index(char c) {
        return c == ' ' ? 26 : c - 'a';
    }

    private void add(String s, int k) {
        count.merge(s, k, Integer::sum);
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            int j = index(s.charAt(i));
            if (node.next[j] == null) node.next[j] = new Node();
            node = node.next[j];
            if (!node.top.contains(s)) node.top.add(s);
            node.top.sort((a, b) -> {
                int ca = count.get(a), cb = count.get(b);
                return ca != cb ? cb - ca : a.compareTo(b);
            });
            if (node.top.size() > 3) node.top.remove(3);
        }
    }
}

Edge cases to test

  • A prefix that matches nothing (and stays empty for the rest of the sentence)
  • Fewer than three matches
  • Ties in count, broken alphabetically (a space sorts before every letter)
  • A typed sentence that already exists, which raises its count
  • A sentence that is a prefix of another, like go and go home

Hints

Hint 1

Keep a map from sentence to count. For a query, every sentence that starts with the typed prefix is a candidate; sort them by (-count, sentence) and take three.

Hint 2

A trie makes the prefix part cheap: keep a pointer to the trie node of the current prefix and move it one character per call.

Hint 3

Counts only ever grow, and only for the sentence being saved. So each trie node can store its own top-3 list and refresh it only along the path of the sentence whose count changed.

FAQ

What is the best time complexity for Design Search Autocomplete System?

Optimal (trie with a top-3 list per node) runs in O(L) per add, O(1) per character typed time and O(T) extra space. A sentence update touches L nodes and sorts a list of at most four at each; a query moves one step and copies at most three strings.

Which pattern does Design Search Autocomplete System use?

It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie (Prefix Tree), Implement Trie ll, Design In-Memory File System.

Is there a brute force solution for Design Search Autocomplete System?

Yes. Brute force (scan every sentence) takes O(N · L + N log N) per call time and O(N · L) space. Store counts in a hash map and the typed text in a builder.

Which edge cases should I test for Design Search Autocomplete System?

A prefix that matches nothing (and stays empty for the rest of the sentence); Fewer than three matches; Ties in count, broken alphabetically (a space sorts before every letter); A typed sentence that already exists, which raises its count; A sentence that is a prefix of another, like go and go home.