Trie

208. 实现 Trie (前缀树)

话不多讲，先上代码

class Trie {
    private static int R = 26;   //基数
    private Node root;

    private static class Node {
        private boolean hasWord = false;
        private Node[] next = new Node[R];
    }

    public Trie() {
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        root = insert(root, word, 0);
    }

    private Node insert(Node x, String key, int d) {
        if (x == null) x = new Node();
        if (d == key.length()) {
            x.hasWord = true;
            return x;
        }
        char c = key.charAt(d);
        x.next[c - 'a'] = insert(x.next[c - 'a'], key, d + 1);
        return x;
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        Node x = search(root, word, 0);
        if (x == null) return false;
        return x.hasWord;
    }

    private Node search(Node x, String key, int d) {
        //返回以x为根节点的子单词查找树中与key相关的值
        if (x == null) return null;
        if (d == key.length()) return x;
        char c = key.charAt(d);
        return search(x.next[c - 'a'], key, d + 1);
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        if (root == null) return false;
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            int c = prefix.charAt(i) - 'a';
            if (cur.next[c] == null) return false;
            cur = cur.next[c];
        }
        return true;
    }
}

Tips

• Trie不会存储任何字符串或字符（隐式），它保存了链接数组和值
• 最坏情况下查找和插入操作的时间界限：在trie中查找一个键或者插入一个键时，访问数组的次数最多为键（String key）的长度加一，所以时间复杂度为O(key.length()+1)。
• 而一棵单词查找树需要多少空间呢？链接总数在RN到RNw之间，其中R是基数（这里是26个字母，故R=26），N为字符串的个数，w为字符串的平均长度