Created
September 14, 2012 02:26
-
-
Save prettymuchbryce/3719435 to your computer and use it in GitHub Desktop.
Dictionary with trie tree Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Dictionary implemented using a Trie Tree. | |
public class Dictionary { | |
private HashMap<Character,Node> roots = new HashMap<Character,Node>(); | |
/** | |
* Search through the dictionary for a word. | |
* @param string The word to search for. | |
* @return Whether or not the word exists in the dictionary. | |
*/ | |
public boolean search(String string) { | |
if (roots.containsKey(string.charAt(0))) { | |
if (string.length()==1 && roots.get(string.charAt(0)).endOfWord) { | |
return true; | |
} | |
return searchFor(string.substring(1),roots.get(string.charAt(0))); | |
} else { | |
return false; | |
} | |
} | |
/** | |
* Insert a word into the dictionary. | |
* @param string The word to insert. | |
*/ | |
public void insert(String string) { | |
if (!roots.containsKey(string.charAt(0))) { | |
roots.put(string.charAt(0), new Node()); | |
} | |
insertWord(string.substring(1),roots.get(string.charAt(0))); | |
} | |
//Recursive method that inserts a new word into the trie tree. | |
private void insertWord(String string, Node node) { | |
final Node nextChild; | |
if (node.children.containsKey(string.charAt(0))) { | |
nextChild = node.children.get(string.charAt(0)); | |
} else { | |
nextChild = new Node(); | |
node.children.put(string.charAt(0), nextChild); | |
} | |
if (string.length() == 1) { | |
nextChild.endOfWord = true; | |
return; | |
} else { | |
insertWord(string.substring(1),nextChild); | |
} | |
} | |
//Recursive method that searches through the Trie Tree to find the value. | |
private boolean searchFor(String string, Node node) { | |
if (string.length()==0) { | |
if (node.endOfWord) { | |
return true; | |
} else { | |
return false; | |
} | |
} | |
if (node.children.containsKey(string.charAt(0))) { | |
return searchFor(string.substring(1),node.children.get(string.charAt(0))); | |
} else { | |
return false; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Node { | |
public Node parent; | |
public Boolean endOfWord = false; //Does this Node mark the end of a particular word? | |
public HashMap<Character,Node> children = new HashMap<Character,Node>(); | |
} |
I prefer TreeMap to store word than HashMap, it automatically sorts all the character
Here's a kotlin implementation spun off of this one: https://gist.github.com/bseib/2c2d2d4745c47353a884a51af0cc4a7d
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
this code is genius. love it! - I'd like to use parts of your logic in an application that I'm making, would that be okay with you?