题目链接：208. 实现 Trie (前缀树) - 力扣（LeetCode）
这应该和图论没啥关系，应该属于哈希和树，题目没讲前缀树到达是啥
前缀树是如何做到高效查找字符串的呢，先说单词查找树吧，一共就只有26个字母，先给节点结构
代码语言：javascript复制 struct Node {
Node*next[26];
};这样存储字符串abc和abcd只会多一个d指向的节点，也就是相同的前缀会在相同的节点，每一个字母会有26种后缀，因此有26个指针指向后缀节点，如果某节点指针为空，说明没有该字母后缀
如果26个指针都为空，说明该节点是末尾节点，但是我们可以增加一个布尔变量标记是否是结尾，而不需要每次遍历判断26个指针
代码语言：javascript复制 struct Node {
vector<Node*>next;
bool end;
Node():next(26,nullptr),end(false){}
};插入字符串的时候，从头到尾安排单词的每个字母，如果不存在当前字母，为它创建一个新的节点
代码语言：javascript复制 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;
}为了判断是否是前缀和存在单词，可以写一个查找前缀的函数，如果前缀存在返回节点指针，代码基本和插入相同，不同的地方在于当不存在当前字母时说明没有该前缀，直接返回空
代码语言：javascript复制 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;
}那么查找前缀就直接调用看看结果是不是空的，查找单词就先看前缀结果是不是空，不是空看看是不是单词结尾
代码语言：javascript复制 bool search(string word) {
Node *result = isPrefix(word);
return result != nullptr && result->end;
}
bool startsWith(string prefix) {
return isPrefix(prefix) != nullptr;
}全部代码
代码语言：javascript复制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;
}
};
