CODEWITHSUNDEEP
javarecursionarraylisttrie
leigero
leigero

Reputation: 3283

Adding values to ArrayList via recursion is erasing the list for every new value added?

I am making a java Trie, which I have finally completed, but I'm adding the getWords() function which will return all of the values inside the Trie.

I'm having a problem with that function. Quick background info: Every character has an 'index' which is actually the entire word, including all the parent characters. When you enter the word "soup" the letter p has a value of isWord = true and index = "soup".

Also the 'children' variable you see is a HashMap and this function is inside the TrieNode class so keep that in mind.

The code giving me trouble:

private List<String> wordList = new ArrayList<String>();

public List<String> getWords(){

   /*Iterate through trie for every value in the hash map.
    Find all words with isWord= true and add that index to wordList
    */

   String word;
   for(Character key : children.keySet()){
       children.get(key).getWords();
       if(children.get(key).isWord == true){
           word = (children.get(key).index);
           wordList.add(word);
           System.out.println(wordList);  //prints list here for test
       }
   }
   System.out.println(wordList);  // prints again for test (second print)
   return wordList;
}

The first print statement prints out ONE word, the current word that the hash map was currently on when isWord was true. The next time it prints (when running recursively) it again prints only that one word.

IE: If you add two words to the trie "soup" and "hello" it would print: hello and soup on their own lines, but the wordList apparently loses the first word when printing the entire list the second time around.

I'm not sure why words are being lost out of the wordList. It should print: "hello" the first time and "hello soup" the second time should it not?

Once the function is done it returns wordList which is totally empty and has nothing in it.

EDIT:

Due to the confusion I'm adding a little visual here. (including all the code for the trie would be too unnecessary).

adding the words "hello" "hi" "soup" to the Trie

gives it the following Structure

The entire trie now has two key value pairs. H and S.

H is the key which contains a whole separate Trie inside of it. inside H are the nodes I and E (for hello and hi)

The S node has an O in it and the O has a U etc. etc.

The recursion is necessary because you may iterate through the hash maps keys and only get S and H. I need the keys of THOSE nodes as well so i do this recursively.

At the end of these prefixes will eventually be the words. Once I reach the word I want to add it to the wordList.

In the end I want to eventually return the wordList

Upvotes: 0

Views: 1641

Answers (1)

laz
laz

Reputation: 28638

This isn't really recursion as you are calling getWords on a different instance of the object instead of this. In the comments, fge is correct in pointing out that the results are being ignored. You will essentially end up with separate lists at each level in the graph of objects where an object only has it's immediate descendant's words. One way to correct this is to create the List at the top level and pass it into the method getWords and have each element add its words to that List.

Upvotes: 1

Related Questions