1from bisect import bisect_left
2
3def suggestedProducts(products, searchWord):
4 products_sorted = sorted(products)
5 ans = []
6
7 for i in range(len(searchWord)):
8 prefix = searchWord[:i+1]
9
10 # Binary search for first index
11 lo = bisect_left(products_sorted, prefix)
12
13 # Collect up to 3 suggestions
14 suggestions = []
15 for j in range(lo, min(lo + 3, len(products_sorted))):
16 if products_sorted[j].startswith(prefix):
17 suggestions.append(products_sorted[j])
18 else:
19 break
20
21 ans.append(suggestions)
22 return ans