LeetCode 1268: Search Suggestions System
Problem Description
Explanation
To solve this problem, we can follow these steps:
- Sort the
productsarray lexicographically. - Iterate over each character in
searchWordand find the products that have a common prefix with the search word. - Add the suggested products to the result list, ensuring that we only include the three lexicographically minimum products if there are more than three matches.
The time complexity of this solution is O(nmlog(m)) where n is the length of products and m is the average length of strings in products. The space complexity is O(n*m) where n is the length of products and m is the average length of strings in products.
Solutions
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> result = new ArrayList<>();
Arrays.sort(products);
for (int i = 1; i <= searchWord.length(); i++) {
String prefix = searchWord.substring(0, i);
List<String> suggested = new ArrayList<>();
int count = 0;
for (String product : products) {
if (product.startsWith(prefix)) {
suggested.add(product);
count++;
}
if (count == 3) break;
}
result.add(suggested);
}
return result;
}
}Loading editor...