-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTrie.java
More file actions
162 lines (141 loc) · 3.57 KB
/
Copy pathTrie.java
File metadata and controls
162 lines (141 loc) · 3.57 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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
/**
* @author Ralph
* a trie tree class, contents are case-insensitive
*/
public class Trie {
TrieNode root;
/**
* number of words that have been added to the Trie
*/
int size;
/**
*Each node has a character, a flag, and up to 26 children.
*Flag will be set to true if it is the node
* that contains last character of a word
*/
class TrieNode {
boolean flag = false;
boolean hasChild = false;
char character;
TrieNode[] children = new TrieNode[26];
public boolean addNodesFor(String word){
char letter = word.charAt(0);
int index = letter - 'a';
if (this.children[index] == null){
this.children[index] = new TrieNode();
//added a character value to the node
this.children[index].character = letter;
}
if (word.length()==1){
this.flag = true;
return true;
}
return this.children[index].addNodesFor(word.substring(1));
}
public boolean nodeContains(TrieNode node, String subString) {
// if (node==null){
// return false;
// }
if (subString.length()==1){
return node.flag;
}
char letter = subString.charAt(0);
int index = letter - 'a';
if (node.children[index]==null){
return false;
}
return node.children[index].nodeContains(node.children[index], subString.substring(1));
}
public boolean nodeContainsPrefix(TrieNode node, String subString) {
// if (node == null){
// return false;
// }
if (subString.isEmpty()){
return true;
}
char letter = subString.charAt(0);
int index = letter - 'a';
if (node.children[index]==null){
return false;
}
return node.children[index].nodeContainsPrefix(node.children[index], subString.substring(1));
}
}
/**
* Constructor for a new Trie
*/
public Trie(){
root = new TrieNode();
}
/**
* Constructor for a new Trie with parameter added as a word
* @param word of type string
*/
public Trie(String word){
root = new TrieNode();
this.add(word);
}
/**
* @param word of type string
* @return true if success (not already stored)
*/
public boolean add(String word){
word=word.toLowerCase();
if (this.contains(word)){
return false;
}
if (word.isEmpty()){
return true;
}
char letter = word.charAt(0);
int index = letter - 'a';
//If child node for the character is not in place->add it
if (root.children[index] == null){
root.children[index] = new TrieNode();
//added a character value to the new node
root.children[index].character = letter;
}
//Child character is in place
size++;
return root.children[index].addNodesFor(word.substring(1));
}
/**
* @param word of type string
* @return true if word is already stored in the Trie
*/
public boolean contains(String word){
word=word.toLowerCase();
char letter = word.charAt(0);
int index = letter - 'a';
if (root.children[index]==null){
return false;
}
return root.nodeContains(root, word);
}
/**
* returns true if pre is the prefix of a word in the tree
* @param pre is a string which represents a prefix
* @return true if trie contains that string
* or false if does not
*/
public boolean containsPrefix(String pre){
pre = pre.toLowerCase();
return this.root.nodeContainsPrefix(this.root,pre);
}
/**
* @return the number of words stored
*/
public int size(){
return size;
}
/**
* clears the Trie by setting all children to null,
* and setting size to 0
*/
public void clear(){
for (int i = 0; i<26; i++){
this.root.children[i] = null;
}
size=0;
}
}