61B-37:overview, Tries

1
2

keysWithPrefix(String prefix) // returns all keys in the trie that start with the given prefix
longestPrefixOf(String query) // returns the longest key in the trie that is a prefix of the query

1
2
3
4
5
6
7
8

private class Node{
    boolean exists;
    Map<Character, Node> links;
    public Node(){
        links = new TreeMap<>();
        exists = false;
    }
}

1
2
3
4
5
6
7

public class TSTSet<Value>{
    private Node<Value> root;
    private static class Node<Value>{
        private char c;
        private Node<Value> lo, mid, hi;
    }
}