Search Suggestions System
Solve this Problemproducts and a searchWord being typed one character at a time, return a list of suggestion lists — one per character typed — where each entry holds up to 3 lexicographically smallest products that still have the typed-so-far prefix.
Sorting the products once turns "find every product with this prefix" into a contiguous block that a binary search can locate directly. Going further, inserting the sorted products into a trie — and letting each node cache the first 3 products that ever pass through it — turns every later query into a plain O(1)-per-character walk with no searching left to do at all: the trie already did the sorting and filtering work once, up front.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ products.length ≤ 1000 - ◆
1 ≤ products[i].length ≤ 20 - ◆
1 ≤ searchWord.length ≤ 20 - ◆
products[i] and searchWord consist of lowercase English letters
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Good — Sort Once, Binary Search Per Prefix
GoodSort all products alphabetically up front — that alone guarantees every product sharing a given prefix sits in one contiguous, already lexicographically-ordered block. For each growing prefix of searchWord, binary search for where that block would start, then just read off up to the next 3 entries that actually still share the prefix. Sorting costs O(n log n) once; each of the L prefixes costs only O(log n) to locate plus O(1) to read off at most 3 results.
O(n log n + L log n)O(n)1class Solution {
2 public String[][] suggestedProducts(String[] products, String searchWord) {
3 Arrays.sort(products);
4 int n = products.length;
5 String[][] result = new String[searchWord.length()][];
6 String prefix = "";
7 for (int i = 0; i < searchWord.length(); i++) {
8 prefix += searchWord.charAt(i);
9 int lo = 0, hi = n;
10 while (lo < hi) {
11 int mid = (lo + hi) / 2;
12 if (products[mid].compareTo(prefix) < 0) lo = mid + 1;
13 else hi = mid;
14 }
15 List<String> suggestions = new ArrayList<>();
16 for (int j = lo; j < n && suggestions.size() < 3; j++) {
17 if (products[j].startsWith(prefix)) {
18 suggestions.add(products[j]);
19 } else {
20 break;
21 }
22 }
23 result[i] = suggestions.toArray(new String[0]);
24 }
25 return result;
26 }
27}Optimal — Trie with Precomputed Top-3
OptimalSort the products first, then insert them into a trie in that sorted order — and while inserting, let every node along the way keep a running list of the first (so, alphabetically smallest) 3 products that ever pass through it. Because insertion happens in sorted order, that cap-of-3 list is already exactly right the moment it's full; nothing needs re-sorting later. A query then just walks searchWord's characters down the trie, reading off each node's precomputed list directly — O(1) per character, falling back to an empty list the instant the path runs out.
O(N + L)O(N)1class Solution {
2 static class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 List<String> suggestions = new ArrayList<>();
5 }
6
7 public String[][] suggestedProducts(String[] products, String searchWord) {
8 Arrays.sort(products);
9 TrieNode root = new TrieNode();
10 for (String product : products) {
11 TrieNode node = root;
12 for (char c : product.toCharArray()) {
13 int idx = c - 'a';
14 if (node.children[idx] == null) {
15 node.children[idx] = new TrieNode();
16 }
17 node = node.children[idx];
18 if (node.suggestions.size() < 3) {
19 node.suggestions.add(product);
20 }
21 }
22 }
23 String[][] result = new String[searchWord.length()][];
24 TrieNode node = root;
25 boolean broken = false;
26 for (int i = 0; i < searchWord.length(); i++) {
27 if (!broken) {
28 int idx = searchWord.charAt(i) - 'a';
29 if (node.children[idx] == null) {
30 broken = true;
31 } else {
32 node = node.children[idx];
33 }
34 }
35 result[i] = broken ? new String[0] : node.suggestions.toArray(new String[0]);
36 }
37 return result;
38 }
39}