Type-Ahead Product Suggestions

medium trie string

Problem

Given a sorted product catalog and a search string, after each prefix the user has typed return up to three lexicographically smallest matching products. Sort once; for each prefix, binary-search for the start and emit the next ≤ 3 entries that still match.

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

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

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

products (comma-separated)

query

def suggestions(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 suggestions(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>> suggestions(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>> suggestions(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;
}

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