LeetCode 208. 实现 Trie (前缀树)

Michael阿明

发布于 2020-07-13 15:29:39

23400

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

参考：Trie树

class Trie
{
private:
    bool isEnd = false;
    Trie* next[26] = { nullptr };
public:
    Trie() {}

    void insert(const string& word)//插入单词
    {
        Trie* root = this;
        for (const auto& w : word) {
            if (root->next[w-'a'] == nullptr)
                root->next[w-'a'] = new Trie();
            root = root->next[w-'a'];
        }
        root->isEnd = true;
    }

    bool search(const string& word)//查找单词
    {
        Trie* root = this;
        for (const auto& w : word) {
            if (root->next[w-'a'] == nullptr)
                return false;
            root = root->next[w-'a'];
        }
        return root->isEnd;
    }

    bool startsWith(string prefix)//查找是否包含该前缀
    {
        Trie* root = this;
        for (const auto& p : prefix) {
            if (root->next[p-'a'] == nullptr)
                return false;
            root = root->next[p-'a'];
        }
        return true;
    }
};