Poison

208. Implement Trie (Prefix Tree)

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
class Trie {

private static class TrieNode {
private static final int R = 26;

private boolean end;
private final TrieNode[] children;

public TrieNode() {
this.end = false;
this.children = new TrieNode[R];
}

public boolean isEnd() {
return this.end;
}

public void setEnd(boolean end) {
this.end = end;
}

public boolean containsChild(char c) {
return children[c - 'a'] != null;
}

public void createChild(char c) {
children[c - 'a'] = new TrieNode();
}

public TrieNode getChild(char c) {
return children[c - 'a'];
}
}

private final TrieNode root;

public Trie() {
this.root = new TrieNode();
}

public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (!node.containsChild(c)) {
node.createChild(c);
}
node = node.getChild(c);
}

node.setEnd(true);
}

public boolean search(String word) {
TrieNode endNode = getNodeByPrefix(word);
return endNode != null && endNode.isEnd();
}

private TrieNode getNodeByPrefix(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);

TrieNode child = node.getChild(c);
if (child == null) {
return null;
} else {
node = child;
}
}

return node;
}

public boolean startsWith(String prefix) {
return getNodeByPrefix(prefix) != null;
}

}
Reference

208. Implement Trie (Prefix Tree)