算法专题之字典树

╰+哭是因爲堅強的太久メ 2023-06-24 12:28 11阅读 0赞

### 文章目录 ###

*  什么是字典树/前缀树
 *  字典树的crud操作的算法实现
 *  练习题

转载自 [https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/][https_leetcode-cn.com_problems_implement-trie-prefix-tree_solution_shi-xian-trie-qian-zhui-shu-by-leetcode]

# 什么是字典树/前缀树 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 1]  
灵魂画手233！！！！

# 字典树的crud操作的算法实现 #

class Trie { 
        private TrieNode root;
        class TrieNode { 
    
        // R links to node children
        private TrieNode[] links;
    
        private final int R = 26;
    
        private boolean isEnd;
    
        public TrieNode() { 
            links = new TrieNode[R];
        }
    
        public boolean containsKey(char ch) { 
            return links[ch -'a'] != null;
        }
        public TrieNode get(char ch) { 
            return links[ch -'a'];
        }
        public void put(char ch, TrieNode node) { 
            links[ch -'a'] = node;
        }
        public void setEnd() { 
            isEnd = true;
        }
        public boolean isEnd() { 
            return isEnd;
        }
       }
        //以上是构建字典树的节点
        /** Initialize your data structure here. */
        public Trie() { 
            root = new TrieNode();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) { 
             TrieNode node = root;
            for (int i = 0; i < word.length(); i++) { 
                char currentChar = word.charAt(i);
                if (!node.containsKey(currentChar)) { 
                    node.put(currentChar, new TrieNode());
                }
                node = node.get(currentChar);
            }
            node.setEnd();
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) { 
            TrieNode node = searchPrefix(word);
           return node != null && node.isEnd();
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) { 
             TrieNode node = searchPrefix(prefix);
            return node != null;
        }
    
    
         // search a prefix or whole key in trie and
        // returns the node where search ends
        private TrieNode searchPrefix(String word) { 
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) { 
               char curLetter = word.charAt(i);
               if (node.containsKey(curLetter)) { 
                   node = node.get(curLetter);
               } else { 
                   return null;
               }
            }
            return node;
        }
    }
    
    /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

# 练习题 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 2]

public class WordDictionary { 
    
        class Node { 
            private Node[] next;
            private boolean isWord;
    
            public Node() { 
                next = new Node[26];
                isWord = false;
            }
        }
    
        private Node root;
    
        /** * Initialize your data structure here. */
        public WordDictionary3() { 
            root = new Node();
        }
    
        /** * Adds a word into the data structure. */
        public void addWord(String word) { 
            int len = word.length();
            Node curNode = root;
            for (int i = 0; i < len; i++) { 
                char curChar = word.charAt(i);
                Node next = curNode.next[curChar - 'a'];
                if (next == null) { 
                    curNode.next[curChar - 'a'] = new Node();
                }
                curNode = curNode.next[curChar - 'a'];
            }
            if (!curNode.isWord) { 
                curNode.isWord = true;
            }
        }
    
        /** * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
        public boolean search(String word) { 
            return match(word, root, 0);
        }
    
        private boolean match(String word, Node node, int start) { 
            if (start == word.length()) { 
                return node.isWord;
            }
            char alpha = word.charAt(start);
            if (alpha == '.') { 
                for (int i = 0; i < 26; i++) { 
                    if (node.next[i] != null && match(word, node.next[i], start + 1)) { 
                        return true;
                    }
                }
                return false;
            } else { 
                if (node.next[alpha - 'a'] == null) { 
                    return false;
    
                }
                return match(word, node.next[alpha - 'a'], start + 1);
            }
        }
    }

[ 数组中两个数的最大异或值][Link 1]

[https_leetcode-cn.com_problems_implement-trie-prefix-tree_solution_shi-xian-trie-qian-zhui-shu-by-leetcode]: https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191228124441548.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191228130536461.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2019122813305243.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDYzMTQx,size_16,color_FFFFFF,t_70
[Link 1]: https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/li-yong-yi-huo-yun-suan-de-xing-zhi-tan-xin-suan-f/