208. 实现 Trie (前缀树)

名字是乱打的

发布于 2021-12-24 08:43:12

3030

发布于 2021-12-24 08:43:12

文章被收录于专栏：软件工程

思路:

这是一种叫做单词查找树的结构。它由字符串键中所有的字符构造而成，允许使用被查找键中的字符进行查找。其中包括插入、查找、删除，寻找前缀等操作. [站外图片上传中...(image-832521-1636112029289)]

代码:

class Trie {
        //定义前缀树结点结构
        public class TrieNode {
            //表示当前节点所能链接到其他节点的个数（在删除操作中会用到）
            public int path;
            //表示以当前节点为结尾的单词的个数
            public int end;
            //表示当前节点能链接到的所有节点。
            public HashMap<Character, TrieNode> next;

            public TrieNode() {
                path = 0;
                end = 0;
                next = new HashMap<>();
            }
        }

        //跟结点
        private TrieNode root;

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

        public void insert(String word) {
            if(word == null || word.length()==0) {
                return ;
            }
            TrieNode node=root;
            for (int i = 0; i < word.length(); i++) {
                char ch=word.charAt(i);
                if (!node.next.containsKey(ch)){
                    node.next.put(ch,new TrieNode());
                }
                node = node.next.get(ch);
                node.path++;
            }
            node.end++;
        }

        public boolean search(String word) {
            if(word==null||word.length()==0) {
                return false;
            }

            TrieNode node=root;
            for (int i = 0; i < word.length(); i++) {
                char currChar=word.charAt(i);
                if (!node.next.containsKey(currChar)){
                    return false;
                }else{
                    node=node.next.get(currChar);
                }
            }
            //如果这个没有以此为截至结点的就返回false
            if (node.end==0){
                return false;
            }
            return true;
        }

        public boolean startsWith(String prefix) {
            if(prefix==null||prefix.length()==0) {
                return false;
            }

            TrieNode node=root;
            for (int i = 0; i < prefix.length(); i++) {
                char currChar=prefix.charAt(i);
                if (!node.next.containsKey(currChar)){
                    return false;
                }else{
                    node=node.next.get(currChar);
                }
            }
            return true;
        }
    }

补充

如果我们有delete操作 delete操作同上述操作大致相同，这里需要使用到path变量，回忆一下，path：表示当前节点所能链接到其他节点的个数。还以五个单词为例，例如删除'the'，当匹配到‘t’时，由于进行path--操作后，此时判断path为0，过可直接将当前节点置空，后面的数据则不用再去遍历即可。java中的垃圾回收机制会处理其他的被断开的节点，如果在C++中，则需要全部匹配，之后调用析构函数去操作

public void delete(String word){
    if(word == null || word.equals("") || !search(word)) return ;
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        char ch = word.charAt(i);
        if(--node.next.get(ch).path == 0){
            node.next.remove(ch);
            return;
        }
        node = node.next.get(ch);
    }
    node.end--;
}