算法训练|实现 Trie (前缀树)

208. 实现 Trie (前缀树) - 力扣（LeetCode）

总结：

Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：

指向子节点的指针数组 children。对于本题而言，数组长度为 26，即小写英文字母的数量。此时 children[0] 对应小写字母 a，children[1]对应小写字母 b，…，children[25]对应小写字母 z。
布尔字段 isEnd\textit{isEnd}isEnd，表示该节点是否为字符串的结尾。（解释来源：leetcode官方）。用来实现查早字符串是否存在以及是否作为字串出现过。需要注意的地方是，每个Trie指针都是指向一整个对象包括了vector和一个bool，而不是指向了vector中的某一个对象。

代码：

class Trie {
public:
    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;
    }
    Trie():children(26,nullptr),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;
    }
};