Search Suggestions System

medium trie string

Problem

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord.

Inputproducts = ["mouse","mobile","mango","mango pie"], query = "mou"

Output[ ["mango","mango pie","mobile"], ["mobile","mouse"], ["mouse"] ]

After typing 'm', 'mo', 'mou'; products narrow at each step.

products (comma-separated)

query

def suggested_products(products, query):
    products.sort()
    out = []
    for i in range(1, len(query) + 1):
        pre = query[:i]
        out.append([p for p in products if p.startswith(pre)][:3])
    return out

function suggestedProducts(products, query) {
  products.sort();
  const out = [];
  for (let i = 1; i <= query.length; i++) {
    const pre = query.slice(0, i);
    const matches = products.filter(p => p.startsWith(pre)).slice(0, 3);
    out.push(matches);
  }
  return out;
}

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String query) {
        Arrays.sort(products);
        List<List<String>> out = new ArrayList<>();
        for (int i = 1; i <= query.length(); i++) {
            String pre = query.substring(0, i);
            List<String> matches = new ArrayList<>();
            for (String p : products) if (p.startsWith(pre)) { matches.add(p); if (matches.size() == 3) break; }
            out.add(matches);
        }
        return out;
    }
}

vector<vector<string>> suggestedProducts(vector<string>& products, string query) {
    sort(products.begin(), products.end());
    vector<vector<string>> out;
    for (int i = 1; i <= (int)query.size(); i++) {
        string pre = query.substr(0, i);
        vector<string> matches;
        for (auto& p : products) if (p.substr(0, pre.size()) == pre) { matches.push_back(p); if (matches.size() == 3) break; }
        out.push_back(matches);
    }
    return out;
}

Explanation

After each letter the user types, we want the three smallest matching product names. The simple, reliable trick is to sort the products once and then, for each growing prefix, scan from the front and grab the first three that start with it.

Why sort first? Because once the list is in alphabetical order, the matches for any prefix are already in the order we want, so the first three we find are the three lexicographically smallest. We never have to sort again.

For each prefix length i, we take pre = query[:i] and keep products where p.startswith(pre), slicing off the first 3 with [:3].

Example: products sorted as mango, mango pie, mobile, mouse, query mou. Prefix m → first three are mango, mango pie, mobile. Prefix mo → mobile, mouse. Prefix mou → mouse.

We collect one such list per prefix and return them all. It is easy to read and exactly matches the expected output.

Time: O(|q|·n) simple variant Space: O(n)