-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
208.java
105 lines (92 loc) · 2.71 KB
/
208.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
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
__________________________________________________________________________________________________
sample 71 ms submission
class Trie {
private boolean isKey;
private Trie[] next;
/**
* Initialize your data structure here.
*/
public Trie() {
isKey = false;
next = new Trie[26];
}
/**
* Inserts a word into the trie.
*/
public void insert(String word) {
char[] w = word.toCharArray();
Trie trie = this;
for (char c : w) {
if (trie.next[c - 'a'] == null) trie.next[c - 'a'] = new Trie();
trie = trie.next[c - 'a'];
}
trie.isKey = true;
}
/**
* Returns if the word is in the trie.
*/
public boolean search(String word) {
char[] w = word.toCharArray();
Trie trie = this;
for (char c : w) {
if (trie.next[c - 'a'] == null) return false;
trie = trie.next[c - 'a'];
}
return trie.isKey;
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String prefix) {
char[] w = prefix.toCharArray();
Trie trie = this;
for (char c : w) {
if (trie.next[c - 'a'] == null) return false;
trie = trie.next[c - 'a'];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
__________________________________________________________________________________________________
sample 48208 kb submission
class Trie {
/** Initialize your data structure here. */
TreeSet<String> set;
public Trie() {
set = new TreeSet<>();
}
/** Inserts a word into the trie. */
public void insert(String word) {
if(!set.contains(word))
set.add(word);
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
return set.contains(word);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
if(set.size()==0)
return false;
String s = set.ceiling(prefix);
if(s!=null)
return s.startsWith(prefix);
else
return false;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
__________________________________________________________________________________________________