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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| class Solution {
private static class Trie {
private final Trie[] children;
private boolean end;
public Trie() {
this.children = new Trie[26];
}
public void add(String word) {
Trie trie = this;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int index = c - 'a';
if (trie.children[index] == null) {
trie.children[index] = new Trie();
}
trie = trie.children[index];
}
trie.end = true;
}
public List<String> search(String word, int limit) {
if (limit < 0) {
throw new IllegalArgumentException("Illegal limit: " + limit);
}
List<String> wordList = new ArrayList<>(3);
Trie trie = this;
for (int i = 0; i < word.length(); i++) {
if (trie == null) {
break;
}
char c = word.charAt(i);
int index = c - 'a';
trie = trie.children[index];
}
StringBuilder sb = new StringBuilder();
sb.append(word);
dfs(trie, wordList, sb);
return wordList;
}
private void dfs(Trie trie, List<String> wordList, StringBuilder sb) {
if (trie == null || wordList.size() == 3) {
return;
}
if (trie.end) {
wordList.add(sb.toString());
if (wordList.size() == 3) {
return;
}
}
for (int i = 0; i < trie.children.length; i++) {
Trie child = trie.children[i];
if (child != null) {
char c = (char) ('a' + i);
sb.append(c);
dfs(child, wordList, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
}
}
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> resultList = new ArrayList<>(searchWord.length());
Trie trie = new Trie();
for (String product : products) {
trie.add(product);
}
for (int i = 0; i < searchWord.length(); i++) {
resultList.add(trie.search(searchWord.substring(0, i + 1), 3));
}
return resultList;
}
}
|
References
1268. Search Suggestions System