208. 实现 Trie (前缀树) - 力扣（LeetCode） (leetcode-cn.com)

 

前缀树（字典树） 是一种多叉树结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查

每个节点存放两个信息：

• chidren 是一个大小为 26 的一维数组，分别对应了26个英文字符 'a' ~ 'z'，也就是说形成了一棵 26叉树
• isEnd 判断树的根节点到当前节点是否构成了一个单词

 

 

 class Trie {
        private Trie[] children;
        private boolean isEnd;
        public Trie() {
            children = new Trie[26]; // 只是定义了一下，没有实例化，相当于树枝在那儿，但是没有链接节点
            isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for(int i=0; i<word.length(); i++){
                char ch = word.charAt(i);
                int index = ch - 'a';
                if(node.children[index] == null){
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;  //当前节点是最后一个
        }

        public boolean search(String word) {
            Trie node = this;   //创建一个Trie对象，即一个新的节点，给节点指向当前字典树的根节点
            for(int i=0; i<word.length(); i++){
                char ch = word.charAt(i);
                int index = ch - 'a';
                if(node.children[index] == null){   //这个位置的节点是空的，那么就要重新创建
                    return false;
                }
                node = node.children[index];   // 将节点下移
            }
            if(node.isEnd == true){
                return true;
            }else {
                return false;
            }
        }

        public boolean startsWith(String prefix) {  //判断前缀
            Trie node = this;
            for(int i=0; i<prefix.length(); i++){
                char ch = prefix.charAt(i);
                int index = ch-'a';
                if(node.children[index] == null){
                    return false;
                }
                node = node.children[index];
            }
            return true;
        }
    }