leetcode 208. Implement Trie (Prefix Tree) | 208. 实现 Trie 前缀树（Java）

绝地灬酷狼 2022-10-06 00:35 233阅读 0赞

## 题目 ##

[https://leetcode.com/problems/implement-trie-prefix-tree/][https_leetcode.com_problems_implement-trie-prefix-tree]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

## 题解 ##

#### 第一版：暴力法 ####

import java.util.LinkedHashSet;
    
    class Trie { 
        LinkedHashSet<String> set;
        /** Initialize your data structure here. */
        public Trie() { 
            set = new LinkedHashSet<>();
        }
    
        /** Inserts a word into the trie. */
        public void insert(String word) { 
            set.add(word);
        }
    
        /** Returns if the word is in the trie. */
        public boolean search(String word) { 
            return set.contains(word);
        }
    
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) { 
            for (String s : set)
                if (s.startsWith(prefix)) return true;
            return false;
        }
    }
    
    /** * 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); */

#### 第二版：前缀树的实现 ####

参考：[官方题解][Link 1]

##### Trie node structure #####

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

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

##### Insertion of a key to a trie #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]

##### Search for a key in a trie #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 5]

##### Search for a key prefix in a trie #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 6]

##### My Code #####

class Node{ 
        Node[] map;
        boolean isEnd;
    
        public Node() { 
            this.map = new Node['z' - 'a' + 1];
        }
    
        public Node get(char c) { 
            return map[c - 'a'];
        }
    
        public Node put(char c) { 
            Node node = new Node();
            map[c - 'a'] = node;
            return node;
        }
    }
    class Trie { 
        Node node;
        /** Initialize your data structure here. */
        public Trie() { 
            node=new Node();
        }
    
        /** Inserts a word into the trie. */
        public void insert(String word) { 
            char[] chars = word.toCharArray();
            Node cur = node;
            for (int i = 0; i < chars.length; i++) { 
                if (cur.get(chars[i]) != null)
                    cur = cur.get(chars[i]);
                else
                    cur = cur.put(chars[i]);
                if (i == chars.length - 1)
                    cur.isEnd = true;
            }
        }
    
        /** Returns if the word is in the trie. */
        public boolean search(String word) { 
            Node 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) { 
            Node node = searchPrefix(prefix);
            return node != null;
        }
    
        public Node searchPrefix(String prefix) { 
            char[] chars = prefix.toCharArray();
            Node cur = node;
            for (char c : chars) { 
                if (cur.get(c) == null) return null;// cur.isEnd可能是伪结束符，不能用来判断是否真正结束遍历
                else cur = cur.get(c);
            }
            return cur;
        }
    }
    
    /** * 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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 7]

--------------------

## 附：左神算法 - 子数组最大异或和 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 8]  
![在这里插入图片描述][20210610140808676.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 11]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 12]

package chapter_5_stringproblem;
    
    public class Problem_24_TrieTree { 
    
    	public static class TrieNode { 
    		public int path;
    		public int end;
    		public TrieNode[] map;
    
    		public TrieNode() { 
    			path = 0;
    			end = 0;
    			map = new TrieNode[26];
    		}
    	}
    
    	public static class Trie { 
    		private TrieNode root;
    
    		public Trie() { 
    			root = new TrieNode();
    		}
    
    		public void insert(String word) { 
    			if (word == null) { 
    				return;
    			}
    			char[] chs = word.toCharArray();
    			TrieNode node = root;
    			node.path++;
    			int index = 0;
    			for (int i = 0; i < chs.length; i++) { 
    				index = chs[i] - 'a';
    				if (node.map[index] == null) { 
    					node.map[index] = new TrieNode();
    				}
    				node = node.map[index];
    				node.path++;
    			}
    			node.end++;
    		}
    
    		public void delete(String word) { 
    			if (search(word)) { 
    				char[] chs = word.toCharArray();
    				TrieNode node = root;
    				node.path--;
    				int index = 0;
    				for (int i = 0; i < chs.length; i++) { 
    					index = chs[i] - 'a';
    					if (node.map[index].path-- == 1) { 
    						node.map[index] = null;
    						return;
    					}
    					node = node.map[index];
    				}
    				node.end--;
    			}
    		}
    
    		public boolean search(String word) { 
    			if (word == null) { 
    				return false;
    			}
    			char[] chs = word.toCharArray();
    			TrieNode node = root;
    			int index = 0;
    			for (int i = 0; i < chs.length; i++) { 
    				index = chs[i] - 'a';
    				if (node.map[index] == null) { 
    					return false;
    				}
    				node = node.map[index];
    			}
    			return node.end != 0;
    		}
    
    		public int prefixNumber(String pre) { 
    			if (pre == null) { 
    				return 0;
    			}
    			char[] chs = pre.toCharArray();
    			TrieNode node = root;
    			int index = 0;
    			for (int i = 0; i < chs.length; i++) { 
    				index = chs[i] - 'a';
    				if (node.map[index] == null) { 
    					return 0;
    				}
    				node = node.map[index];
    			}
    			return node.path;
    		}
    	}
    
    	public static void main(String[] args) { 
    		Trie trie = new Trie();
    		System.out.println(trie.search("zuo"));
    		trie.insert("zuo");
    		System.out.println(trie.search("zuo"));
    		trie.delete("zuo");
    		System.out.println(trie.search("zuo"));
    		trie.insert("zuo");
    		trie.insert("zuo");
    		trie.delete("zuo");
    		System.out.println(trie.search("zuo"));
    		trie.delete("zuo");
    		System.out.println(trie.search("zuo"));
    		trie.insert("zuoa");
    		trie.insert("zuoac");
    		trie.insert("zuoab");
    		trie.insert("zuoad");
    		trie.delete("zuoa");
    		System.out.println(trie.search("zuoa"));
    		System.out.println(trie.prefixNumber("zuo"));
    
    	}
    
    }

[https_leetcode.com_problems_implement-trie-prefix-tree]: https://leetcode.com/problems/implement-trie-prefix-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/c1e1fb74fc354a9aa5ac0f13c8cb391d.png
[Link 1]: https://leetcode.com/problems/implement-trie-prefix-tree/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/e6dccc7c667d4eb08cd05c8096d57fb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/945ea02dc95d48faab3c956942562f63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]: /images/20221005/797d8d3293734d859dc96e32a5037f46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 4]: /images/20221005/cd432ed6b3db4c6eb9197b3590156d7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 5]: /images/20221005/2f29085ae8564786b388078b8ab2ccc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 6]: /images/20221005/de9c9f3da40e4ac8ab8c416c8cbe2e65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 7]: /images/20221005/697cf0ed722647c8a254ba475ccc0766.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 8]: /images/20221005/ddb024b515764fd589cb52e320bb7b8e.png
[20210610140808676.png]: /images/20221005/a1f50385100241a58b57b15f4e18793e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 9]: /images/20221005/f0ac76e0564f4af9941c598f049a44ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 10]: /images/20221005/3691dccee5534227975899e31ad26821.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 11]: /images/20221005/f3a9d57da1994349956a857530132207.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 12]: /images/20221005/08e4e51d16dc4b6bbeb28ad2c36d10c9.png