/
SuggestedProducts.java
41 lines (34 loc) · 1.19 KB
/
SuggestedProducts.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// https://leetcode.com/problems/search-suggestions-system
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> res = new ArrayList<>();
TrieNode head = new TrieNode(), t = head;
for (String p: products) {
for (char c: p.toCharArray()) {
if (t.children[c - 'a'] == null) {
t.children[c - 'a'] = new TrieNode();
}
t.children[c - 'a'].words.add(p);
t = t.children[c - 'a'];
}
t = head;
}
for (char c: searchWord.toCharArray()) {
Set<String> words;
if (t != null) {
t = t.children[c - 'a'];
}
if (t != null) {
words = t.words;
} else {
words = Set.of();
}
res.add(words.stream().limit(3).collect(Collectors.toList()));
}
return res;
}
class TrieNode {
TrieNode[] children = new TrieNode[26];
Set<String> words = new TreeSet<>();
}
}