题目描述（中等难度）

实现 Trie 数，即前缀树。trie的发明者 Edward Fredkin 把它读作 /ˈtriː/ "tree"。但是，其他作者把它读作/traɪ/"try"。

解法一

算作一个高级的数据结构，实现方式可以通过 26 叉树。每个节点存一个字母，根节点不存字母。

"app" "as" "cat" "yes" "year" "you"
              root
          /    |    \
         a     c      y
        / \    |     / \
       p   s   a    e   o
      /        |   / \   \
     p         t  s   a   u
                      |
                      r     
上图中省略了 null 节点，对于第一层画完整了其实是下边的样子, 图示中用 0 代表 null
                                   root
         / | | | | | | | | | | | | | | | | | | | | | | | | \
        a  0 c 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 y  0          
其它层同理

代码的话，我们定义一个节点，每个节点包含一个节点数组，代表 26 个孩子。此外，还需要一个 flag 变量来标记当前节点是否是某个单词的结束。

class TrieNode {
    TrieNode[] children;
    boolean flag;
    public TrieNode() {
        children = new TrieNode[26];
        flag = false;
        //节点初始化为 null
        for (int i = 0; i < 26; i++) {
            children[i] = null;
        }
    }
}

然后只需要实现题目中所需要的三个函数即可。其中 children[0] 存 a， children[1] 存 b， children[2] 存 c... 依次类推。所以存的时候我们用当前字符减去 a ，从而得到相应的 children 下标。

class Trie {
    class TrieNode {
        TrieNode[] children;
        boolean flag;
        public TrieNode() {
            children = new TrieNode[26];
            flag = false;
            for (int i = 0; i < 26; i++) {
                children[i] = null;
            }
        }
    }

    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            //当前孩子是否存在
            if (cur.children[array[i] - 'a'] == null) {
                cur.children[array[i] - 'a'] = new TrieNode();
            }
            cur = cur.children[array[i] - 'a'];
        }
        //当前节点代表结束
        cur.flag = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        char[] array = word.toCharArray();
        TrieNode cur = root;
        for (int i = 0; i < array.length; i++) {
            //不含有当前节点
            if (cur.children[array[i] - 'a'] == null) {
                return false;
            }
            cur = cur.children[array[i] - 'a'];
        }
        //当前节点是否为是某个单词的结束
        return cur.flag;
    }

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

};

总

只要知道每个节点存字母，路径代表单词，代码就很好写出来了。

前缀树适用于两个场景。

• 统计每个单词出现的次数，代码的话只需要将上边的 flag 改成 int 类型，然后每次插入的时候计数即可。

  当然，我们用 HashMap 也可以做到，key 是单词，value 存这个单词出现的次数即可。但缺点是，当单词很多很多的时候，受到 Hash 函数的影响，hash 值会经常出现冲突，算法可能退化为 O(n)，n 是 key 的总数。

  而对于前缀树，我们查找一个单词出现的次数，始终是 O(m)，m 为单词的长度。

• 查找某个前缀的单词，最常见的比如搜索引擎的提示、拼写检查、ip 路由等。