算法思路

Trie 树又叫字典树、前缀树、单词查找树，是一种二叉树衍生出来的高级数据结构，主要应用场景是处理字符串前缀相关的操作。

Trie 树的核心数据结构是多叉树。TrieNode中children数组的索引是有意义的，代表键中的一个字符。

比如说children[97]如果非空，说明这里存储了一个字符'a'，因为'a'的 ASCII 码为 97。

/* Trie 树节点实现 */
class TrieNode<V> {
    V val = null;
    TrieNode<V>[] children = new TrieNode[256];
}

代码实现

class TrieMap<V>{
    private static final int R = 256;
    private int size = 0;
    private static class TrieNode<V> {
        V val = null;
        TrieNode<V>[] children = new TrieNode[R];
    }

    private TrieNode<V> root = null;

    private TrieNode<V> getNode(TrieNode<V> node, String key){
        TrieNode<V> p = node;
        for(int i = 0; i < key.length(); i++){
            if(p == null){
                return null;
            }
            char c = key.charAt(i);
            p = p.children[c];
        }
        return p;
    }

    private V get(String key){
        TrieNode<V> x = getNode(root, key);
        if(x == null || x.val == null){
            return null;
        }
        return x.val;
    }

    public boolean containsKey(String key){
        return get(key) != null;
    }

    public boolean startsWith(String prefix){
        return getNode(root, prefix) != null;
    }

    public void put(String key, V val){
        if(!containsKey(key)){
            size++;
        }
        root = put(root, key, val, 0);
    }

    private TrieNode<V> put(TrieNode<V> node, String key, V val, int i){
        if(node == null){
            node = new TrieNode<V>();
        }
        if(i == key.length()){
            node.val = val;
            return node;
        }
        char c = key.charAt(i);
        node.children[c] = put(node.children[c], key, val, i + 1);
        return node;
    }

    public int size(){
        return size;
    }
}