前缀树Tire

208.实现Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

代码模板如下：

class Trie {
    /*
    总体思路:
    1.创建节点类:TireNode 包含2个成员:
        1.boolean end->标记该节点是否为单词末尾
        2.TireNode[26] children 孩子触手指向接下来的字母节点
    2.通过这个TireNode类进行保存、查找与查询前缀的操作
        */
    class TireNode {
        boolean end;    // 标记该节点是否为单词末尾
        TireNode[] children;    // 孩子触手指向接下来的字母节点

        public TireNode() {
            end = false;    // 默认不是结尾
            children = new TireNode[26];    // 保存字母26只触手即可
        }
    }

    TireNode root;  // Tire根节点

    public Trie() {
        root = new TireNode();
    }

    // 向前缀树中插入字符串 word
    public void insert(String word) {
        TireNode p = root; // p指针从Tire根节点开始
        for (int i = 0; i < word.length(); i++) {
            int u = word.charAt(i) - 'a';   // word[i]对应触手索引
            if (p.children[u] == null) p.children[u] = new TireNode();  // 没有对应字母节点就创建
            p = p.children[u];  // 往下走
        }
        p.end = true;   // 标记p这里是结尾
    }

    // 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false
    public boolean search(String word) {
        TireNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int u = word.charAt(i) - 'a';
            if (p.children[u] == null) return false;    // 没有该单词
            p = p.children[u];
        }
        return p.end;   // 如果当初p标记了结尾说明就是存在该单词
    }

    // 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false
    public boolean startsWith(String prefix) {
        TireNode p = root;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (p.children[u] == null) return false;
            p = p.children[u];
        }
        return true;    // 能走完就表明存在该前缀,不一定要为end==true
    }
}