-
Notifications
You must be signed in to change notification settings - Fork 2
/
TrieNode.java
125 lines (104 loc) · 3.11 KB
/
TrieNode.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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
package utils;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class TrieNode {
//keeping the child chars in a tree map so that the child nodes
//can be retrieved in a sorted order. helps with some questions.
private Map<Character, TrieNode> nodeMap = new TreeMap<>();
private String word = null;
boolean containsChar(final Character character) {
return nodeMap.containsKey(character);
}
public void addNode(Character ch) {
if (!nodeMap.containsKey(ch)) {
nodeMap.put(ch, new TrieNode());
}
}
public TrieNode getNode(Character ch) {
return nodeMap.get(ch);
}
public String getWord() {
return word;
}
public void setWord(String strWord) {
this.word = strWord;
}
public Set<Character> getChildChars() {
return nodeMap.keySet();
}
public void removeChar(Character c) {
nodeMap.remove(c);
}
public TrieNode getChildNode(Character ch) {
return nodeMap.get(ch);
}
public Map<Character, TrieNode> getAllChildNodes() {
return nodeMap;
}
public void buildTrie(Object[] words) {
for (Object word : words) {
buildTrie((String) word);
}
}
public void buildTrie(String[] words) {
for (String word : words) {
buildTrie(word);
}
}
public void buildTrie(String word) {
buildTrie(word, 0);
}
private void buildTrie(String word, int index) {
if (word.length() <= index) {
return;
}
Character ch = word.charAt(index);
addNode(ch);
TrieNode child = getNode(ch);
if (word.length() - 1 == index) {
child.setWord(word);
} else {
child.buildTrie(word, index + 1);
}
}
public boolean search(String word) {
return search(0, word, false);
}
public boolean searchPrefix(String word) {
return search(0, word, true);
}
private boolean search(int index, String word, boolean prefixOnly) {
if (prefixOnly && index == word.length() - 1) {
return nodeMap.containsKey(word.charAt(index));
}
if (index == word.length()) {
return this.word != null;
}
TrieNode node = nodeMap.get(word.charAt(index));
if (node == null) {
return false;
} else {
return node.search(index + 1, word, prefixOnly);
}
}
public boolean searchWithDot(int index, String word) {
if (index == word.length()) {
return this.word != null;
}
if (word.charAt(index) == '.') {
for (TrieNode childNode : nodeMap.values()) {
boolean found = childNode.searchWithDot(index + 1, word);
if (found) return true;
}
return false;
} else {
TrieNode node = nodeMap.get(word.charAt(index));
if (node == null) {
return false;
} else {
return node.searchWithDot(index + 1, word);
}
}
}
}