LeetCode 208. 实现 Trie (前缀树)

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

参考：Trie树

代码语言：javascript复制

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;
    }
};

insert search trie

0 人点赞