Search Suggestions System
MedPrompt
You are given an array of strings products and a string searchWord.
Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return a list of lists of the suggested products after each character of searchWord is typed.
Example 1:
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
After typing mou, mous and mouse the system suggests ["mouse","mousepad"].Example 2:
Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Explanation: The only word "havana" will be always suggested while typing the search word.
Constraints:
1 <= products.length <= 10001 <= products[i].length <= 30001 <= sum(products[i].length) <= 2 * 104- All the strings of
productsare unique. products[i]consists of lowercase English letters.1 <= searchWord.length <= 1000searchWordconsists of lowercase English letters.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach simulates the process directly. For each character typed, it forms the current prefix. It then iterates through the entire list of products, collecting all products that start with this prefix. Finally, it sorts the collected matches and picks the top three.
Algorithm
- Initialize an empty list of lists
result. - Initialize an empty string
prefix. - Iterate through each character
cofsearchWord:- Append
ctoprefix. - Create an empty list
suggestions. - Iterate through each
productin theproductsarray:- If
productstarts withprefix, addproducttosuggestions.
- If
- Sort
suggestionslexicographically. - Create a new list
currentResult. - Add the first
min(3, suggestions.size())elements fromsuggestionstocurrentResult. - Add
currentResulttoresult.
- Append
- Return
result.
Walkthrough
We iterate from the first character of searchWord up to its full length.
In each iteration i, we consider the prefix p = searchWord.substring(0, i+1).
We create a temporary list, matches.
We loop through every product in the products array.
For each product, we check if it startsWith(p). If it does, we add it to matches.
After checking all products, we sort the matches list lexicographically.
We then take the first 3 elements from the sorted matches list (or all of them if there are fewer than 3) and add this sublist to our final result.
This process is repeated for all prefixes of searchWord.
class Solution { public List<List<String>> suggestedProducts(String[] products, String searchWord) { List<List<String>> result = new ArrayList<>(); StringBuilder prefix = new StringBuilder(); for (char c : searchWord.toCharArray()) { prefix.append(c); List<String> matches = new ArrayList<>(); for (String product : products) { if (product.startsWith(prefix.toString())) { matches.add(product); } } Collections.sort(matches); List<String> suggestions = new ArrayList<>(); for (int i = 0; i < Math.min(3, matches.size()); i++) { suggestions.add(matches.get(i)); } result.add(suggestions); } return result; }}Complexity
Time
O(M * (N*L + N log N * L)), where `M` is the length of `searchWord`, `N` is the number of products, and `L` is the maximum length of a product. For each of the `M` prefixes, we iterate through `N` products (`O(N)`), each `startsWith` check takes up to `O(L)` time, and sorting `N` products takes `O(N log N * L)`. This is highly inefficient.
Space
O(N * L), where N is the number of products and L is their maximum length. This space is required to store the matching products for each prefix before sorting and trimming.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very slow, especially for long search words and large product lists.
It recomputes and re-sorts for every single character typed, leading to a lot of redundant work.
Solutions
Solution
class Trie { Trie [] children = new Trie [ 26 ]; List < Integer > v = new ArrayList <>(); public void insert ( String w , int i ) { Trie node = this ; for ( int j = 0 ; j < w . length (); ++ j ) { int idx = w . charAt ( j ) - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; if ( node . v . size () < 3 ) { node . v . add ( i ); } } } public List < Integer >[] search ( String w ) { Trie node = this ; int n = w . length (); List < Integer >[] ans = new List [ n ]; Arrays . setAll ( ans , k -> new ArrayList <>()); for ( int i = 0 ; i < n ; ++ i ) { int idx = w . charAt ( i ) - 'a' ; if ( node . children [ idx ] == null ) { break ; } node = node . children [ idx ]; ans [ i ] = node . v ; } return ans ; } } class Solution { public List < List < String >> suggestedProducts ( String [] products , String searchWord ) { Arrays . sort ( products ); Trie trie = new Trie (); for ( int i = 0 ; i < products . length ; ++ i ) { trie . insert ( products [ i ], i ); } List < List < String >> ans = new ArrayList <>(); for ( var v : trie . search ( searchWord )) { List < String > t = new ArrayList <>(); for ( int i : v ) { t . add ( products [ i ]); } ans . add ( t ); } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.