【LeetCode热题100】【图论】实现 Trie (前缀树)

叶茂林

发布于 2024-04-21 08:38:47

680

发布于 2024-04-21 08:38:47

文章被收录于专栏：叶子的开发者社区

题目链接：208. 实现 Trie (前缀树) - 力扣（LeetCode）

这应该和图论没啥关系，应该属于哈希和树，题目没讲前缀树到达是啥

前缀树是如何做到高效查找字符串的呢，先说单词查找树吧，一共就只有26个字母，先给节点结构

    struct Node {
        Node*next[26];
    };

这样存储字符串abc和abcd只会多一个d指向的节点，也就是相同的前缀会在相同的节点，每一个字母会有26种后缀，因此有26个指针指向后缀节点，如果某节点指针为空，说明没有该字母后缀

如果26个指针都为空，说明该节点是末尾节点，但是我们可以增加一个布尔变量标记是否是结尾，而不需要每次遍历判断26个指针

    struct Node {
        vector<Node*>next;
        bool end;
        Node():next(26,nullptr),end(false){}
    };

插入字符串的时候，从头到尾安排单词的每个字母，如果不存在当前字母，为它创建一个新的节点

    Node *tree;

    void insert(string word) {
        Node *node = tree;
        for (char letter: word) {
            letter -= 'a';
            if (node->next[letter] == nullptr)
                node->next[letter] = new Node();
            node = node->next[letter];
        }
        node->end = true;
    }

为了判断是否是前缀和存在单词，可以写一个查找前缀的函数，如果前缀存在返回节点指针，代码基本和插入相同，不同的地方在于当不存在当前字母时说明没有该前缀，直接返回空

    Node *isPrefix(string &prefix) {
        Node *node = tree;
        for (char letter: prefix) {
            letter -= 'a';
            if (node->next[letter] == nullptr)
                return nullptr;
            node = node->next[letter];
        }
        return node;
    }

那么查找前缀就直接调用看看结果是不是空的，查找单词就先看前缀结果是不是空，不是空看看是不是单词结尾

    bool search(string word) {
        Node *result = isPrefix(word);
        return result != nullptr && result->end;
    }

    bool startsWith(string prefix) {
        return isPrefix(prefix) != nullptr;
    }

全部代码

class Trie {
    struct Node {
        vector<Node *> next;
        bool end;

        Node(): next(26, nullptr), end(false) {
        }
    };

    Node *tree;

public:
    Trie(): tree(new Node()) {
    }

    void insert(string word) {
        Node *node = tree;
        for (char letter: word) {
            letter -= 'a';
            if (node->next[letter] == nullptr)
                node->next[letter] = new Node();
            node = node->next[letter];
        }
        node->end = true;
    }

    Node *isPrefix(string &prefix) {
        Node *node = tree;
        for (char letter: prefix) {
            letter -= 'a';
            if (node->next[letter] == nullptr)
                return nullptr;
            node = node->next[letter];
        }
        return node;
    }

    bool search(string word) {
        Node *result = isPrefix(word);
        return result != nullptr && result->end;
    }

    bool startsWith(string prefix) {
        return isPrefix(prefix) != nullptr;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-04-20，如有侵权请联系 cloudcommunity@tencent.com 删除

字符串