Trie树学习

柔光的暖阳◎ 2022-01-27 00:37 245阅读 0赞

为了解决问题：  
为了解决字符串存取查找的问题，将时间复杂度降低到根据查找的字符以字符串的长度的情况来查找。  
Trie树的定义：

public class Trie {
    
        private class Node{
    
            public boolean isWord;
    
            public TreeMap<Character,Node> next;
    
            public Node(boolean isWord){
                this.isWord = isWord;
                next = new TreeMap<>();
    
            }
    
            public Node(){
                this(false);
    
            }
    
        }
        private Node root;
    
        private int size;
    
        public Trie()
        {
            root  = new Node();
            size = 0;
        }
        //获取Trie中存储的单词
        public int getSize(){
            return size;
        }

首先定义Node节点，每一个Node节点以TreeMap来定义，同时伴随着一个boolean标志，Tire树包含一个Node类型的root根节点,同时含有一个int类型的计算操作。也可以将Node节点下的TreeMap给替换成其他的。用TreeMap防止形成单链表的情况。

添加单词操作：

//添加单词
        public void add(String word){
    
            Node cur = root;
            for(int i=0;i<word.length();i++){
    
                char c = word.charAt(i);
                if(cur.next.get(c)==null)
                    cur.next.put(c,new Node());
                cur = cur.next.get(c);
    
            }
            //cur 最后一个字符所处的节点
            if(!cur.isWord) {
                cur.isWord = true;
                size++;
            }
        }

即通过判断cur.next.get©每一个字符存在吗?来判断添加吗？同时还要对最后一个字符的isWord置true.

查询方法

public boolean contains(String word){
    
            Node cur = root;
            for(int i = 0;i<word.length();i++){
                char c = word.charAt(i);
                if(cur.next.get(c)==null)
                    return false;
                cur = cur.next.get(c);
            }
            return cur.isWord;
        }

前缀是否包含

//查询是否在Trie中有单词以prefix为前缀
        public boolean isPrefix(String prefix){
            Node cur = root;
            for(int i =0 ;i<prefix.length();i++)
            {
                 char c = prefix.charAt(i);
                 if(cur.next.get(c)==null){
    
                     return false;
                 }
                 cur = cur.next.get(c);
    
            }
            return true;
    
        }

查询和前缀是否包含，这个基本逻辑差不多。在传入前缀是否包含当前cur.next.get©==null,return false; 而在查询时，return cur.isWord. 为啥不是return false呢？因为，还可能存在在最后一个字符底下还存在其他字符的情况。

附带  
leetcode 211

//leetcode 211
        public boolean search(String word){
    
            return match(root,word,0);
        }
        private  boolean match(Node node,String word,int index){
            if(index == word.length())
                return node.isWord;
    
            char c = word.charAt(index);
            if(c!='.'){
                if(node.next.get(c)==null){
                    return false;
                    return match(node.next.get(c),word,index+1);
                }else{
                    for(char nextChar:node.next.keySet())
                        if(match(node.next.get(nextChar),word,index+1));
                            return true;
                            return false;
                }
            }
    
        }