Trie
princeton
public class Trie<Value> {
private class Node {
private Node[] next = (Node []) new Object[R];
private Value value;
}
private static final int R =256;
private Node root = new Node();
private int size = 0;
public void put(String s, Value value) {
put(root, s, 0, value);
}
public Node put(Node root, String s, int index, Value value) {
if (root == null) {
root = new Node();
}
if (s.length() == index) {
root.value = value;
size++;
return root;
}
char c = s.charAt(index);
root.next[c] = put(root.next[c], s, index + 1, value);
return root;
}
public Value get(String s) {
return get(root, s, 0);
}
public Value get(Node root, String s, int index) {
if (root == null) {
return null;
}
if (s.length() == index) {
return root.value;
}
char c = s.charAt(index);
return get(root.next[c], s, index + 1);
}
public boolean contains(String s) {
return get(s) != null;
}
public Iterable<String> keys() {
return keysWithPrefix("");
}
public Iterable<String> keysWithPrefix(String prefix) {
Queue<String> results = new Queue<String>();
Node x = get(root, prefix, 0);
collect(x, new StringBuilder(prefix), results);
return results;
}
private void collect(Node x, StringBuilder prefix, Queue<String> results) {
if (x == null) return;
if (x.val != null) results.enqueue(prefix.toString());
for (char c = 0; c < R; c++) {
prefix.append(c);
collect(x.next[c], prefix, results);
prefix.deleteCharAt(prefix.length() - 1);
}
}
}