-
-
Save awreese/16888cff2badb73e21fc4399953234f3 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))); | |
} | |
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; | |
} | |
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) { | |
return node.endOfWord; | |
} | |
if (node.children.containsKey(string.charAt(0))) { | |
return searchFor(string.substring(1),node.children.get(string.charAt(0))); | |
} | |
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 { | |
// private Node parent; // never used | |
private Boolean endOfWord = false; //Does this Node mark the end of a particular word? | |
private HashMap<Character,Node> children = new HashMap<Character,Node>(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment