Search Suggestions System

mediumTrie & Strings124 stepsJava · Python · C++

After each typed character, suggest up to three products with that prefix, in alphabetical order. Sort the products once. For each prefix, binary-search the first product ≥ the prefix; the next three products that still start with it are the suggestions.

▶ Watch the animated trace

Traced input: products = [mobile, mouse, moneypot, monitor, mousepad], searchWord = mouse → [["mobile", "moneypot", "monitor"], ["mobile", "moneypot", "monitor"], ["mouse", "mousepad"], ["mouse", "mousepad"], ["mouse", "mousepad"]]. Original problem: leetcode.com/problems/search-suggestions-system/

Complexity

BestO(n log n)

AverageO(n log n + L log n)

WorstO(n log n + L log n)

SpaceO(1)

Sorting plus one binary search per typed character.

Key idea

In sorted order, all products sharing a prefix are contiguous.
The first one is found by binary search (lower bound).
Take up to three from there while they match the prefix.
A trie storing the top three at each node is the other common solution.

Common mistakes

Forgetting to sort first.
Taking three products without checking they still match the prefix.

Solution

Java

List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Arrays.sort(products);
    List<List<String>> res = new ArrayList<>();
    String prefix = "";
    for (char c : searchWord.toCharArray()) {
        prefix += c;
        int lo = 0, hi = products.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (products[mid].compareTo(prefix) < 0) lo = mid + 1;
            else hi = mid;
        }
        List<String> top = new ArrayList<>();
        for (int i = lo; i < Math.min(lo + 3, products.length) && products[i].startsWith(prefix); i++) top.add(products[i]);
        res.add(top);
    }
    return res;
}

Python

def suggestedProducts(products: List[str], searchWord: str) -> List[List[str]]:
    products.sort()
    res, prefix = [], ""
    for c in searchWord:
        prefix += c
        lo = bisect.bisect_left(products, prefix)
        res.append([p for p in products[lo:lo + 3] if p.startswith(prefix)])
    return res

C++

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
    sort(products.begin(), products.end());
    vector<vector<string>> res;
    string prefix;
    for (char c : searchWord) {
        prefix += c;
        auto it = lower_bound(products.begin(), products.end(), prefix);
        vector<string> top;
        for (int i = 0; i < 3 && it != products.end() && it->compare(0, prefix.size(), prefix) == 0; i++, it++) top.push_back(*it);
        res.push_back(top);
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No matches No product starts with 't'.	`products = [havana], searchWord = tatiana`	`[[], [], [], [], [], [], []]`
Fewer than three Only one product ever matches.	`products = [havana], searchWord = havana`	`[["havana"], ["havana"], ["havana"], ["havana"], ["havana"], ["havana"]]`