Search Suggestions System

1public List<List<String>> suggestedProducts(String[] products, String searchWord) {
2    Arrays.sort(products);
3    List<List<String>> ans = new ArrayList<>();
4
5    for (int i = 0; i < searchWord.length(); i++) {
6        String prefix = searchWord.substring(0, i + 1);
7
8        // Binary search for first index
9        int lo = binarySearch(products, prefix);
10
11        // Collect up to 3 suggestions
12        List<String> suggestions = new ArrayList<>();
13        for (int j = lo; j < Math.min(lo + 3, products.length); j++) {
14            if (products[j].startsWith(prefix)) {
15                suggestions.add(products[j]);
16            } else {
17                break;
18            }
19        }
20
21        ans.add(suggestions);
22    }
23    return ans;
24}
25
26private int binarySearch(String[] products, String target) {
27    int left = 0, right = products.length;
28    while (left < right) {
29        int mid = left + (right - left) / 2;
30        if (products[mid].compareTo(target) < 0) {
31            left = mid + 1;
32        } else {
33            right = mid;
34        }
35    }
36    return left;
37}