Trie字典树 (处理字符串）

曾经终败给现在 2021-09-24 00:58 303阅读 0赞

# 主要用于处理字符串，将字符串一个一个拆开。 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]

import java.util.TreeMap;
    
    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;
        }
    
        // 向Trie中添加一个新的单词word
        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);
            }
    
            if(!cur.isWord){ 
                cur.isWord = true;
                size ++;
            }
        }
    
        // 查询单词word是否在Trie中
        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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200316131354187.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: /images/20210923/a3e20ed3c42c4ceaac475db8cd056692.png