I am attempting to implement a very simple Trie in Java that supports 3 operations. I'd like it to have an insert method, a has method (ie is a certain word in the trie), and a toString method to return the trie in string form. I believe I have insertion working properly, but has and toString are proving to be difficult. Here's what I have so far.
The trie class.
public class CaseInsensitiveTrie implements SimpleTrie {
//root node
private TrieNode r;
public CaseInsensitiveTrie() {
r = new TrieNode();
}
public boolean has(String word) throws InvalidArgumentUosException {
return r.has(word);
}
public void insert(String word) throws InvalidArgumentUosException {
r.insert(word);
}
public String toString() {
return r.toString();
}
public static void main(String[] args) {
CaseInsensitiveTrie t = new CaseInsensitiveTrie();
System.out.println("Testing some strings");
t.insert("TEST");
t.insert("TATTER");
System.out.println(t.has("TEST"));
}
}
And the node class
public class TrieNode {
//make child nodes
private TrieNode[] c;
//flag for end of word
private boolean flag = false;
public TrieNode() {
c = new TrieNode[26]; //1 for each letter in alphabet
}
protected void insert(String word) {
int val = word.charAt(0) - 64;
//if the value of the child node at val is null, make a new node
//there to represent the letter
if (c[val] == null) {
c[val] = new TrieNode();
}
//if word length > 1, then word is not finished being added.
//otherwise, set the flag to true so we know a word ends there.
if (word.length() > 1) {
c[val].insert(word.substring(1));
} else {
c[val].flag = true;
}
}
public boolean has(String word) {
int val = word.charAt(0) - 64;
if (c[val]!=null && word.length()>1) {
c[val].has(word.substring(1));
} else if (c[val].flag==true && word.length()==1) {
return true;
}
return false;
}
public String toString() {
return "";
}
}
So basically, when creating a Trie, a TrieNode is created as the root with 26 children. When an insert is attempted, insert is called on that root node, which recursively creates a new node at the correct position, and continues until the word is complete. I believe that method is working properly.
My has function is very broken, because I have to have that return statement outside of the brackets for some reason. I cannot contain it within an else clause or the compiler complains. Other than that, I am thinking that method should work with some tweaks, but I cannot figure it out for the life of me.
toString is a beast I have tried to tackle, but nothing I throw at it works, so I will leave that be until I solve the has problem. If I get has working I may be able to figure a way to reformat it into a toString function.
The purpose of the int val = word.charAt(0) - 64; is because each string entered must be all caps (I will create a string formatting function to ensure this afterwards) so the first letter's int value - 64 will be it's position in the array. ie array index 0 is A, so A = 64, A - 64 = 0. B = 65, B - 64 = 1, and so on.
int val = word.charAt(0) - 64;you do:int val = word.charAt(0) - 'A';! – Hoopes