Skip to content

Instantly share code, notes, and snippets.

@prettymuchbryce
Created September 14, 2012 02:26
Show Gist options
  • Save prettymuchbryce/3719435 to your computer and use it in GitHub Desktop.
Save prettymuchbryce/3719435 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)));
} 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;
}
}
}
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>();
}
@awreese
Copy link

awreese commented Dec 8, 2016

-Node should be private inner-class so as not to expose internal data, or at least have private fields with package exposure
-Should remove useless last if-else branches since there isn't any code afterwards and just return false at the end of methods
-Use Boolean Zen when returning true/false based on node.endOfWord, i.e. just return node.endOfWord

@mithuns my guess is the parent field of nodes is there for future reverse searches of words.

@LAlvarez11
Copy link

Whats the time complexity of this?

Copy link

ghost commented Jul 5, 2017

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?

@nguyenhungquang
Copy link

I prefer TreeMap to store word than HashMap, it automatically sorts all the character

@bseib
Copy link

bseib commented Jul 1, 2020

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