Given a list of products and a searchWord, for each character typed in searchWord return up to 3 lexicographically smallest product suggestions starting with that prefix.
Input: products=["mobile","mouse","moneypot","monitor","mousepad"], searchWord="mouse" → Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Sort products. For each prefix, binary search to find the first matching product, then take up to 3 products starting with that prefix.
- Sort products.
- For each prefix (length 1..n): binary search for first product >= prefix.
- Collect up to 3 products that start with the current prefix.
import java.util.*;
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
List<List<String>> result = new ArrayList<>();
String prefix = "";
for (char c : searchWord.toCharArray()) {
prefix += c;
int idx = Arrays.binarySearch(products, prefix);
if (idx < 0) idx = -idx - 1;
List<String> suggestions = new ArrayList<>();
for (int i = idx; i < Math.min(idx+3, products.length); i++) {
if (products[i].startsWith(prefix)) suggestions.add(products[i]);
else break;
}
result.add(suggestions);
}
return result;
}
}
- Time Complexity: O(N log N + L log N) where L=searchWord length
- Space Complexity: O(N) for sorting