Leetcode 208. implement trie (prefix tree) (2022.07.27)

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 Call the number A total of No more than 3 * 10⁴ Time

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

C++ Submission ：

class Trie {
    
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
    
        Trie* node = this;
        for (char ch : prefix) {
    
            ch -= 'a';
            if (node->children[ch] == nullptr) {
    
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {
    }

    void insert(string word) {
    
        Trie* node = this;
        for (char ch : word) {
    
            ch -= 'a';
            if (node->children[ch] == nullptr) {
    
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
    
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
    
        return this->searchPrefix(prefix) != nullptr;
    }
};

/** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */