Skip to content

Instantly share code, notes, and snippets.

@pavelfusu
Created July 18, 2013 01:28
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save pavelfusu/cf0fa70af468b3fe5abe to your computer and use it in GitHub Desktop.
public class Trie {
private Map<String, Node> roots = new HashMap<>();
public Trie() {}
public Trie(List<String> argInitialWords) {
for (String word:argInitialWords) {
addWord(word);
}
}
public void addWord(String argWord) {
addWord(argWord.toCharArray());
}
public void addWord(char[] argWord) {
Node currentNode = null;
if (!roots.containsKey(Character.toString(argWord[0]))) {
roots.put(Character.toString(argWord[0]), new Node(argWord[0], "" + argWord[0]));
}
currentNode = roots.get(Character.toString(argWord[0]));
for (int i = 1; i < argWord.length; i++) {
if (currentNode.getChild(argWord[i]) == null) {
currentNode.addChild(new Node(argWord[i], currentNode.getValue() + argWord[i]));
}
currentNode = currentNode.getChild(argWord[i]);
}
currentNode.setIsWord(true);
}
public boolean containsPrefix(String argPrefix) {
return contains(argPrefix.toCharArray(), false);
}
public boolean containsWord(String argWord) {
return contains(argWord.toCharArray(), true);
}
public Node getWord(String argString) {
Node node = getNode(argString.toCharArray());
return node != null && node.isWord() ? node : null;
}
public Node getPrefix(String argString) {
return getNode(argString.toCharArray());
}
@Override
public String toString() {
return roots.toString();
}
private boolean contains(char[] argString, boolean argIsWord) {
Node node = getNode(argString);
return (node != null && node.isWord() && argIsWord) || (!argIsWord && node != null) ? true : false;
}
private Node getNode(char[] argString) {
Node currentNode = roots.get(Character.toString(argString[0]));
for (int i = 1; i < argString.length && currentNode != null; i++) {
currentNode = currentNode.getChild(argString[i]);
if (currentNode == null) {
return null;
}
}
return currentNode;
}
}
public class Node {
private final Character ch;
private final String value;
private Map<String, Node> children = new HashMap<>();
private boolean isValidWord;
public Node(char argChar, String argValue) {
ch = argChar;
value = argValue;
}
public boolean addChild(Node argChild) {
if (children.containsKey(Character.toString(argChild.getChar()))) {
return false;
}
children.put(Character.toString(argChild.getChar()), argChild);
return true;
}
public boolean containsChildValue(char c) {
return children.containsKey(Character.toString(c));
}
public String getValue() {
return value.toString();
}
public char getChar() {
return ch;
}
public Node getChild(char c) {
return children.get(Character.toString(c));
}
public boolean isWord() {
return isValidWord;
}
public void setIsWord(boolean argIsWord) {
isValidWord = argIsWord;
}
public String toString() {
return value;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment