Skip to content

Instantly share code, notes, and snippets.

@spacanowski
Last active October 24, 2016 14:47
Show Gist options
  • Save spacanowski/a5bf74c1a2df60bfd33da74c62e4bb29 to your computer and use it in GitHub Desktop.
Save spacanowski/a5bf74c1a2df60bfd33da74c62e4bb29 to your computer and use it in GitHub Desktop.
Java trie implementation
public class Trie {
private int childValueLength = 1;
private Map<String, Node> children = new HashMap<>();
public void add(String value) {
add(this, value);
}
private void add(Trie node, String value) {
if (node.childValueLength == value.length()) {
if (!node.children.containsKey(value)) {
node.children.put(value, new Node(value));
} else {
throw new IllegalStateException("Value already exists");
}
} else {
String valuePart = value.substring(0, node.childValueLength);
if (node.children.containsKey(valuePart)) {
add(node.children.get(valuePart), value);
} else {
Node partNode = new Node(valuePart);
node.children.put(valuePart, partNode);
add(partNode, value);
}
}
}
public Node find(String value) {
return find(this, value);
}
private Node find(Trie node, String value) {
if (node.childValueLength > value.length()) {
return null;
}
String valuePart = value.substring(0, node.childValueLength);
if (node.children.containsKey(valuePart)) {
Node child = node.children.get(valuePart);
if (valuePart.length() == value.length()) {
return child;
} else if (valuePart.length() < value.length()) {
return find(child, value);
}
}
return null;
}
private static class Node extends Trie {
private final String value;
private Node(String value) {
this.value = value;
super.childValueLength = value.length() + 1;
}
@Override
public String toString() {
return value;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment