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

本文主要是介绍【LeetCode热题100】【图论】实现 Trie (前缀树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：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;}
};

这篇关于【LeetCode热题100】【图论】实现 Trie (前缀树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---