StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POTrie implementation
text
Body
copied!<p>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.</p> <p>The trie class.</p> <pre><code> 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")); } } </code></pre> <p>And the node class</p> <pre><code> 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 ""; } } </code></pre> <p>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.</p> <p>My has function is very broken, because I <em>have</em> 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.</p> <p>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.</p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload