208. 实现 Trie (前缀树)

2023.11.6

        前缀树本质上是一颗26叉树，对应着26个英文字母。其结构中需要定义两个信息：①一个节点数组child，存储了当前节点的所有子节点。②一个Boolean型变量，用于表示从根节点到当前节点为止，该路径是否形成了一个有效的字符串。

        构造函数Trie即初始化一个大小为26的节点数组child，再将Boolean型变量初始化为false。

        insert方法则需要遍历word字符串中的每个字符，若当前字符对应的子节点在节点数组child中没出现过，则添加一个新子节点到数组child对应位置上，然后继续搜索下一个字符对应的子节点；若当前字符对应的子节点出现过，则直接搜索下一个字符对应的子节点。

        search方法需要从根开始查找有无对应的字符串。依然是遍历word字符串的每个字符，若当前字符对应的节点在数组child中没有出现，直接返回false；如果出现了，则继续搜索下一个字符对应的子节点是否出现，直到遍历完毕。 最后判断一下当前节点的Boolean型变量isEnd是否为true，如果为true说明以当前节点结尾的字符串是一个有效的字符串，返回true，否则返回false。

        startsWith方法用来判断是否出现了对应前缀，代码和search差不多，唯一区别就是遍历完之后不需要判断isEnd，遍历完都没有返回false的话就直接返回true即可。

        java代码如下：

class Trie {
    private Trie[] child;
    private boolean isEnd;
 
    public Trie() {
        child = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for(int i=0; i
            char c = word.charAt(i);
            int index = c - 'a';
            if(node.child[index] == null){
                node.child[index] = new Trie();
            }
            node = node.child[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = this;
        for(int i=0; i
            char c = word.charAt(i);
            int index = c - 'a';
            if(node.child[index] == null){
                return false;
            }
            node = node.child[index];
        }
        return node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        Trie node = this;
        for(int i=0; i
            char c = prefix.charAt(i);
            int index = c - 'a';
            if(node.child[index] == null){
                return false;
            }
            node = node.child[index];
        }
        return true;
    }
}