Java Getting a list of words from a Trie?

The simplest solution is to use a depth-first search You go down the trie, matching letter by letter from the input. Then, once you have no more letter to match, everything under that node are strings that you want. Recursively explore that whole subtrie, building the string as you go down to its nodes.

The simplest solution is to use a depth-first search. You go down the trie, matching letter by letter from the input. Then, once you have no more letter to match, everything under that node are strings that you want.

Recursively explore that whole subtrie, building the string as you go down to its nodes.

This is easier to solve recursively in my opinion. It would go something like this: Write a recursive function Print that prints all the nodes in the trie rooted in the node you give as parameter. Wiki tells you how to do this (look at sorting).

Find the last character of your prefix, and the node that is labeled with the character, going down from the root in your trie. Call the Print function with this node as the parameter. Then just make sure you also output the prefix before each word, since this will give you all the words without their prefix.

If you don't really care about efficiency, you can just run Print with the main root node and only print those words that start with the prefix you're interested in. This is easier to implement but slower.

You need to traverse the sub-tree starting at the node you found for the prefix. Start in the same way, i.e. Finding the correct node.

Then, instead of checking its marker, traverse that tree (i.e. Go over all its descendants; a DFS is a good way to do it) , saving the substring used to reach the "current" node from the first node. If the current node is marked as a word, output* the prefix + substring reached.

* or add it to a list or something.

You would need to use a List List myList = new ArrayList(); if(matchingStringFound) myList. Add(stringToAdd).

After your for loop, add a call to printAllStringsInTrie(current, s); void printAllStringsInTrie(Node t, String prefix) { if (t. Current_marker) System.out. Println(prefix); for (int I = 0; I Length; i++) { if (t.

Childi! = null) { printAllStringsInTrie(t. Childi, prefix + ('a' + i)); // does + work on (String, char)?

} } }.

I built a trie once for one of ITA puzzles public class WordTree { class Node { private final char ch; /** * Flag indicates that this node is the end of the string. */ private boolean end; private LinkedList children; public Node(char ch) { this. Ch = ch; } public void addChild(Node node) { if (children == null) { children = new LinkedList(); } children.

Add(node); } public Node getNode(char ch) { if (children == null) { return null; } for (Node child : children) { if (child.getChar() == ch) { return child; } } return null; } public char getChar() { return ch; } public List getChildren() { if (this. Children == null) { return Collections.emptyList(); } return children; } public boolean isEnd() { return end; } public void setEnd(boolean end) { this. End = end; } } Node root = new Node(' '); public WordTree() { } /** * Searches for a strings that match the prefix.

* * @param prefix - prefix * @return - list of strings that match the prefix, or empty list of no matches are found. */ public List getWordsForPrefix(String prefix) { if (prefix.length() == 0) { return Collections.emptyList(); } Node node = getNodeForPrefix(root, prefix); if (node == null) { return Collections.emptyList(); } List> chars = collectChars(node); List words = new ArrayList(chars.size()); for (LinkedList charList : chars) { words. Add(combine(prefix.

Substring(0, prefix.length() - 1), charList)); } return words; } private String combine(String prefix, List charList) { StringBuilder sb = new StringBuilder(prefix); for (Character character : charList) { sb. Append(character); } return sb.toString(); } private Node getNodeForPrefix(Node node, String prefix) { if (prefix.length() == 0) { return node; } Node next = node. GetNode(prefix.

CharAt(0)); if (next == null) { return null; } return getNodeForPrefix(next, prefix. Substring(1, prefix.length())); } private List> collectChars(Node node) { List> chars = new ArrayList>(); if (node.getChildren().size() == 0) { chars. Add(new LinkedList(Collections.

SingletonList(node.getChar()))); } else { if (node.isEnd()) { chars. Add(new LinkedList(Collections. SingletonList(node.getChar()))); } List children = node.getChildren(); for (Node child : children) { List> childList = collectChars(child); for (LinkedList characters : childList) { characters.

Push(node.getChar()); chars. Add(characters); } } } return chars; } public void addWord(String word) { addWord(root, word); } private void addWord(Node parent, String word) { if (word.trim().length() == 0) { return; } Node child = parent. GetNode(word.

CharAt(0)); if (child == null) { child = new Node(word. CharAt(0)); parent. AddChild(child); } if (word.length() == 1) { child.

SetEnd(true); } else { addWord(child, word. Substring(1, word.length())); } } public static void main(String args) { WordTree tree = new WordTree(); tree. AddWord("world"); tree.

AddWord("work"); tree. AddWord("wolf"); tree. AddWord("life"); tree.

AddWord("love"); System.out. Println(tree. GetWordsForPrefix("wo")); } }.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.