Skip to content

Instantly share code, notes, and snippets.

@awreese
Forked from prettymuchbryce/Dictionary.java
Last active December 8, 2016 17:19
Show Gist options
  • Save awreese/16888cff2badb73e21fc4399953234f3 to your computer and use it in GitHub Desktop.
Save awreese/16888cff2badb73e21fc4399953234f3 to your computer and use it in GitHub Desktop.
Dictionary with trie tree Java
//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;
}
}
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