字典树（前缀树）哈希表实现（能查所有字符）

Node2类：表示Trie树的节点。每个节点有三个属性：

pass：表示经过该节点的次数，即有多少个字符串经过了这个节点。
end：表示以该节点结尾的字符串数量，即有多少个字符串在这个节点结束。
nexts：是一个HashMap，用于存储指向下一个节点的映射。键是字符的ASCII码，值是对应的下一个节点。


Trie2类：实现了具体的Trie树功能。它有一个根节点root，以及以下方法：

insert(String word)：向Trie树中插入一个字符串。首先将字符串转换为字符数组，然后从根节点开始遍历字符数组，对于每个字符，如果当前节点的nexts映射中没有对应的节点，就创建一个新的节点并添加到映射中。最后，将最后一个字符对应的节点的end计数加一。
delete(String word)：从Trie树中删除一个字符串。首先检查该字符串是否存在，如果存在，则按照插入的顺序逆序遍历字符数组，对于每个字符，将对应节点的pass计数减一，如果某个节点的pass计数变为0，说明没有其他字符串经过这个节点，可以将其从映射中移除。最后，将最后一个字符对应的节点的end计数减一。
search(String word)：在Trie树中查找一个字符串。首先将字符串转换为字符数组，然后从根节点开始遍历字符数组，对于每个字符，如果在当前节点的nexts映射中找不到对应的节点，说明该字符串不存在于Trie树中，返回0。否则，继续遍历下一个字符。最后，返回最后一个字符对应的节点的end计数，表示有多少个字符串以该字符串结尾。
prefixNumber(String pre)：计算有多少个字符串的前缀与给定的前缀相同。首先将前缀转换为字符数组，然后从根节点开始遍历字符数组，对于每个字符，如果在当前节点的nexts映射中找不到对应的节点，说明没有字符串的前缀与给定的前缀相同，返回0。否则，继续遍历下一个字符。最后，返回最后一个字符对应的节点的pass计数，表示有多少个字符串的前缀与给定的前缀相同。

import java.util.HashMap;

public class test6 {
    public static class Node2{
        public int pass;
        public int end;
        public HashMap<Integer , Node2> nexts;


        public Node2(){
            pass = 0;
            end = 0;
            nexts = new HashMap<>();
        }
    }

    public static class Trie2{
        private Node2 root;

        public Trie2(){
            root = new Node2();
        }

        public void insert(String word){
            if(word == null){
                return;
            }
            char[] chs = word.toCharArray();
            Node2 node = root;
            node.pass++;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                if(!node.nexts.containsKey(index)){
                    node.nexts.put(index , new Node2());
                }
                node = node.nexts.get(index);
                node.pass++;
            }
            node.end++;
        }

        public void delete(String word){
            if(search(word) != 0){
                char[] chs =  word.toCharArray();
                Node2 node = root;
                node.pass--;
                int index =0;
                for (int i = 0; i < chs.length; i++) {
                    index = (int) chs[i];
                    if(--node.nexts.get(index).pass == 0){
                        node.nexts.remove(index);
                        return;
                    }
                    node = node.nexts.get(index);
                }
                node.end--;
            }
        }

        public int search(String word){
            if(word == null){
                return 0;
            }
            char[] chs  = word.toCharArray();
            Node2 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                if(!node.nexts.containsKey(index)){
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.end;
        }

        public int prefixNumber(String pre){
            if(pre == null){
                return 0;
            }
            char[] chs =pre.toCharArray();
            Node2 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = (int) chs[i];
                if(!node.nexts.containsKey(index)){
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.pass;
        }
    }
}

原文地址：https://blog.csdn.net/2401_83010439/article/details/140589892

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！