LeetCode_ Prefix tree_ Medium_ 208. implement trie (prefix tree)

1. subject

Trie（ It sounds like “try”） Or say Prefix tree It's a tree data structure , Keys for efficient storage and retrieval of string datasets . This data structure has quite a number of application scenarios , For example, automatic completion and spelling check .

Please realize Trie class ：

Trie()  Initialize the prefix tree object .
void insert(String word)  Insert a string into the forward tree  word .
boolean search(String word)  If the string  word  In the prefix tree , return  true（ namely , Has been inserted before retrieval ）; otherwise , return  false .
boolean startsWith(String prefix)  If a string has been inserted before  word  One of the prefixes of is  prefix , return  true ; otherwise , return  false .

Example ：

 Input 
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
 Output 
[null, null, true, false, true, null, true]
 explain 
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   //  return  True
trie.search("app");     //  return  False
trie.startsWith("app"); //  return  True
trie.insert("app");
trie.search("app");     //  return  True

Tips ：
1 <= word.length, prefix.length <= 2000
word and prefix It's only made up of lowercase letters
insert、search and startsWith The total number of calls does not exceed 3 * 10⁴ Time

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/implement-trie-prefix-tree

2. Ideas

（1） Prefix tree
Train of thought reference Official solution to this problem .
A prefix tree is essentially a multitree derived from a binary tree , But it is different from the previous ordinary multi tree nodes , In its nodes children The index of an array makes sense , It represents a character in the key .

3. Code implementation （Java）

// Ideas 1———— Prefix tree 
class Trie {
    
    private Trie[] children;
    private boolean isEnd;
    
    public Trie() {
    
    	// Each node has at most  26  Child node , They correspond to each other  26  Lowercase letters 
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
    
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
    
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
    
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
    
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
    
        return searchPrefix(prefix) != null;
    }
    
    public Trie searchPrefix(String prefix) {
    
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
    
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
    
                return null;
            }
            node = node.children[index];
        }
        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); */