Getting a list of words from Trie

Question

I want to use the following code not to check if there is a word match in Trie, but to return a list of all words starting with a prefix entered by the user. Can someone point me in the right direction? I can't get it to work at all.

public boolean search(String s) { Node current = root; System.out.println("\nSearching for string: "+s); while(current != null) { for(int i=0;i<s.length();i++) { if(current.child[(int)(s.charAt(i)-'a')] == null) { System.out.println("Cannot find string: "+s); return false; } else { current = current.child[(int)(s.charAt(i)-'a')]; System.out.println("Found character: "+ current.content); } } // If we are here, the string exists. // But to ensure unwanted substrings are not found: if (current.marker == true) { System.out.println("Found string: "+s); return true; } else { System.out.println("Cannot find string: "+s +"(only present as a substring)"); return false; } } return false; } } 

Answer 1

I ran into this problem while trying to make a text autocomplete module. I solved the problem by running Trie, in which each node contains its parent node, as well as its children. First I searched for node, starting with the input prefix. Then I applied Traversal to Trie, which examines all the nodes of the subtree with its root as the node prefix. whenever a node leaf is encountered, this means that the end of the word has been found, starting with the input prefix. Starting from this leaf node, I iterate over the parent nodes, getting the parent element of the parent element, and get the root of the subtree. In doing so, I continued to add node keys to the stack. In the end, I took the prefix and started adding it, pushing the stack. I continued to store words in an ArrayList. At the end of the traversal, I get all the words, starting with the input prefix. Here is the code with an example of use:

 class TrieNode { char c; TrieNode parent; HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>(); boolean isLeaf; public TrieNode() {} public TrieNode(char c){this.c = c;} } 

-

 public class Trie { private TrieNode root; ArrayList<String> words; TrieNode prefixRoot; String curPrefix; public Trie() { root = new TrieNode(); words = new ArrayList<String>(); } // Inserts a word into the trie. public void insert(String word) { HashMap<Character, TrieNode> children = root.children; TrieNode crntparent; crntparent = root; //cur children parent = root for(int i=0; i<word.length(); i++) { char c = word.charAt(i); TrieNode t; if(children.containsKey(c)){ t = children.get(c);} else { t = new TrieNode(c); t.parent = crntparent; children.put(c, t); } children = t.children; crntparent = t; //set leaf node if(i==word.length()-1) t.isLeaf = true; } } // Returns if the word is in the trie. public boolean search(String word) { TrieNode t = searchNode(word); if(t != null && t.isLeaf){return true;} else{return false;} } // Returns if there is any word in the trie // that starts with the given prefix. public boolean startsWith(String prefix) { if(searchNode(prefix) == null) {return false;} else{return true;} } public TrieNode searchNode(String str) { Map<Character, TrieNode> children = root.children; TrieNode t = null; for(int i=0; i<str.length(); i++) { char c = str.charAt(i); if(children.containsKey(c)) { t = children.get(c); children = t.children; } else{return null;} } prefixRoot = t; curPrefix = str; words.clear(); return t; } /////////////////////////// void wordsFinderTraversal(TrieNode node, int offset) { // print(node, offset); if(node.isLeaf==true) { //println("leaf node found"); TrieNode altair; altair = node; Stack<String> hstack = new Stack<String>(); while(altair != prefixRoot) { //println(altair.c); hstack.push( Character.toString(altair.c) ); altair = altair.parent; } String wrd = curPrefix; while(hstack.empty()==false) { wrd = wrd + hstack.pop(); } //println(wrd); words.add(wrd); } Set<Character> kset = node.children.keySet(); //println(node.c); println(node.isLeaf);println(kset); Iterator itr = kset.iterator(); ArrayList<Character> aloc = new ArrayList<Character>(); while(itr.hasNext()) { Character ch = (Character)itr.next(); aloc.add(ch); //println(ch); } // here you can play with the order of the children for( int i=0;i<aloc.size();i++) { wordsFinderTraversal(node.children.get(aloc.get(i)), offset + 2); } } void displayFoundWords() { println("_______________"); for(int i=0;i<words.size();i++) { println(words.get(i)); } println("________________"); } }// 

Example

 Trie prefixTree; prefixTree = new Trie(); prefixTree.insert("GOING"); prefixTree.insert("GONG"); prefixTree.insert("PAKISTAN"); prefixTree.insert("SHANGHAI"); prefixTree.insert("GONDAL"); prefixTree.insert("GODAY"); prefixTree.insert("GODZILLA"); if( prefixTree.startsWith("GO")==true) { TrieNode tn = prefixTree.searchNode("GO"); prefixTree.wordsFinderTraversal(tn,0); prefixTree.displayFoundWords(); } if( prefixTree.startsWith("GOD")==true) { TrieNode tn = prefixTree.searchNode("GOD"); prefixTree.wordsFinderTraversal(tn,0); prefixTree.displayFoundWords(); } 

Answer 2

The simplest solution is to use depth-to-depth search .

You go down the trie, matching the letter with the letter from the entrance. Then, as soon as you no longer have the letters to match, all that is under this node is the lines you want. Recursively explore this whole subtree by building a line when you go down to its nodes.

Answer 3

This is easier to solve recursively, in my opinion. It will look something like this:

• Write a recursive Print function that prints all the nodes in the trie embedded in the node that you specify as a parameter. The wiki tells you how to do this (look at the sort).
• Find the last character of your prefix and the node that is marked with the symbol, descending from the root in your trie. Call the Print function with this node as a parameter. Then just make sure that you also output a prefix before each word, as this will give you all the words without their prefix.

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

Answer 4

You need to go through the tree starting with the node that you found for the prefix.

Start the same way i.e. finding the correct node. Then, instead of checking its marker, traverse this tree (i.e., iterate over all its descendants, DFS is a good way to do this), preserving the substring used to reach the "current" node from the first node.

If the current node is marked as a word, output * prefix + substring.

* or add it to the list or something like that.

Answer 5

After creating Trie, you can do DFS starting with node, where you find the prefix:

 Here Node is Trie node, word=till now found word, res = list of words def dfs(self, node, word, res): # Base condition: when at leaf node, add current word into our list if EndofWord at node: res.append(word) return # For each level, go deep down, but DFS fashion # add current char into our current word. for w in node: self.dfs(node[w], word + w, res) 

Answer 6

You will need to use List List<String> myList = new ArrayList<String>();
if(matchingStringFound)
myList.add(stringToAdd); List<String> myList = new ArrayList<String>();
if(matchingStringFound)
myList.add(stringToAdd);

Answer 7

After the 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 < t.child.length; i++) { if (t.child[i] != null) { printAllStringsInTrie(t.child[i], prefix + ('a' + i)); // does + work on (String, char)? } } } 

Answer 8

I built a trie once for one of the ITA puzzles

open class WordTree {

 class Node { private final char ch; /** * Flag indicates that this node is the end of the string. */ private boolean end; private LinkedList<Node> children; public Node(char ch) { this.ch = ch; } public void addChild(Node node) { if (children == null) { children = new LinkedList<Node>(); } 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<Node> 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<String> getWordsForPrefix(String prefix) { if (prefix.length() == 0) { return Collections.emptyList(); } Node node = getNodeForPrefix(root, prefix); if (node == null) { return Collections.emptyList(); } List<LinkedList<Character>> chars = collectChars(node); List<String> words = new ArrayList<String>(chars.size()); for (LinkedList<Character> charList : chars) { words.add(combine(prefix.substring(0, prefix.length() - 1), charList)); } return words; } private String combine(String prefix, List<Character> 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<LinkedList<Character>> collectChars(Node node) { List<LinkedList<Character>> chars = new ArrayList<LinkedList<Character>>(); if (node.getChildren().size() == 0) { chars.add(new LinkedList<Character>(Collections.singletonList(node.getChar()))); } else { if (node.isEnd()) { chars.add(new LinkedList<Character>(Collections.singletonList(node.getChar()))); } List<Node> children = node.getChildren(); for (Node child : children) { List<LinkedList<Character>> childList = collectChars(child); for (LinkedList<Character> 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")); } 

}

Answer 9

Here is the implementation in C ++

https://github.com/dchavezlive/Basic-Trie

In your search function, you can return its node, where the prefix ends. If you make sure that your node has a field for saving each child (vector?), You can list all the children from this node, where your prefix ends.

Answer 10

The recursive code below can be used where your TrieNode looks like this: This code works great.

 TrieNode(char c) { this.con=c; this.isEnd=false; list=new ArrayList<TrieNode>(); count=0; } //-------------------------------------------------- public void Print(TrieNode root1, ArrayList<Character> path) { if(root1==null) return; if(root1.isEnd==true) { //print the entire path ListIterator<Character> itr1=path.listIterator(); while(itr1.hasNext()) { System.out.print(itr1.next()); } System.out.println(); return; } else{ ListIterator<TrieNode> itr=root1.list.listIterator(); while(itr.hasNext()) { TrieNode child=itr.next(); path.add(child.con); Print(child,path); path.remove(path.size()-1); } }