I'm trying to implement a method that will store all words in a Trie data structure in a List.
This is my Node class:
class Node { char c; HashMap<Character, Node> children = new HashMap<Character, Node>(); boolean isCompleteWord; public Node(char c) { this.c = c; isCompleteWord = false; } public Node() { } }
I am using a HashMap to store the child characters as keys and the child nodes as values. A node that completes a word will have the field isCompleteWord set to true.
Methods to add all words to a List:
List<String> collectWords(char c) { List<String> words = new ArrayList<>(); String word = Character.toString(c); Node node = root.children.get(c); collectWordsHelper(words, node, word); return words; } void collectWordsHelper(List<String> words, Node node, String word) { for (char i = 'a'; i <= 'z'; i++) { if (node.children.containsKey(i)) { System.out.println(i); // prints the right letters Node child = node.children.get(i); word += i; if (child.isCompleteWord && !words.contains(word)) { words.add(word); collectWordsHelper(words, child, ""); } collectWordsHelper(words, child, word); } } }
Currently if I have stored in the Trie the words "beard", "bold", "brew", when I print the list of words starting with the prefix "b", I get:
[beard, beold, beorew]
What I was expecting
[beard, bold, brew]
I think I need a way for the String word to be reset whenever I have found a word, instead of the next characters being appended.