Search Suggestions System
Medium Trie with top-3 lists
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
As each character of searchWord is typed, return up to three product names (alphabetically smallest) that start with the typed prefix.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: up to 3 suggestions for every prefix typed.
Why this works: insert sorted products; each node keeps the first three words passing through it.
Example: products ["mobile","mouse","moneypot","monitor","mousepad"], type "mouse"
"m" → mobile, moneypot, monitor"mou" → mouse, mousepad
✦Hints open one at a time
↗Approach
Build the trie from sorted products, appending each word to a node's list while the list has fewer than 3 entries. Then walk searchWord; once a character has no child, every later answer is empty.
</>Solution (Java)
import java.util.*;
class Solution {
private static class Node {
Node[] next = new Node[26];
List<String> top = new ArrayList<>();
}
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
Node root = new Node();
for (String p : products) {
Node cur = root;
for (char c : p.toCharArray()) {
if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
cur = cur.next[c - 'a'];
if (cur.top.size() < 3) cur.top.add(p); // sorted order: first 3 are smallest
}
}
List<List<String>> res = new ArrayList<>();
Node cur = root;
for (char c : searchWord.toCharArray()) {
cur = (cur == null) ? null : cur.next[c - 'a'];
res.add(cur == null ? new ArrayList<>() : cur.top);
}
return res;
}
}!Common mistake
Forgetting to keep adding empty lists after the prefix stops matching.
- Time: O(total characters + m log m) for sorting.
- Space: O(total characters).