-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTries.java
More file actions
126 lines (98 loc) · 3.04 KB
/
Copy pathTries.java
File metadata and controls
126 lines (98 loc) · 3.04 KB
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
126
public class Tries {
// The absolute root
private TrieNode root;
Tries() {
root = new TrieNode('\0');
}
public static void main(String args[]){
Tries trie = new Tries();
trie.add("not");
trie.add("note");
trie.add("news");
System.out.println(trie.search("not"));
trie.remove("not");
System.out.println(trie.search("not"));
}
public void add(String word) {
add(root, word);
}
private void add(TrieNode node, String word) {
if (word.length() == 0) {
node.isTerminating = true;
return;
}
int firstIndex = word.charAt(0) - 'a';
TrieNode firstNode = node.children[firstIndex];
if (firstNode == null) {
// Create a node and put into it.
firstNode = new TrieNode(word.charAt(0));
node.children[firstIndex] = firstNode;
}
// Node already exits, now we just have to move to the next character.
add(firstNode, word.substring(1));
}
public boolean search(String word) {
return search(root, word);
}
private boolean search(TrieNode node, String word) {
if (word.length() == 0) {
if (node.isTerminating)
return true;
else
return false;
}
int firstIndex = word.charAt(0) - 'a';
if (node.children[firstIndex] == null) {
return false;
}
boolean searchNext = search(node.children[firstIndex], word.substring(1));
return searchNext;
}
public void remove(String word) {
/*
* We first have to find the word- If the word exits,
* just mark it's isTerminating as false.
* No we do not have to increase complexity
* by calling search function first.
*/
remove(root, word);
}
public void remove(TrieNode node, String word){
if(word.length() == 0){
node.isTerminating = false;
return;
}
int firstIndex = word.charAt(0) - 'a';
TrieNode firstNode = node.children[firstIndex];
if(firstNode == null) return;
remove(firstNode, word.substring(1));
}
public class TrieNode {
private char data;
private boolean isTerminating;
private TrieNode[] children;
TrieNode(char data) {
this.data = data;
this.isTerminating = false;
this.children = new TrieNode[26];
}
public void setData(char data) {
this.data = data;
}
public void setTerminating(boolean isTerminating) {
this.isTerminating = isTerminating;
}
public void setChildren(TrieNode[] children) {
this.children = children;
}
public char getData() {
return data;
}
public boolean isTerminating() {
return isTerminating;
}
public TrieNode[] getChildren() {
return children;
}
}
}