208. 实现 Trie (前缀树)
实现一个 Trie (前缀树)，包含
insert,search, 和startsWith这三个操作。
思路：
前缀数也叫字典树，是根据依据字符串的前缀构建的树，经典实现用字母代表边，可以用来查询：
- 是否存在某个字符串以某个字符串开始
- 是否真实加入过某个字符串，加入了几次，而不是是否有字符串包含该字符串
*有多少个字符串以某个字符串为前缀
class Trie {
struct TrieNode //定义前缀树的结点
{
int path; //表示该结点被经过多少次
int end; //表示有字符串以该结点结尾
TrieNode *next[26]; //通往26个英文小写字母
TrieNode()
{
path = 0;
end = 0;
for (int i = 0; i < 26; i++)
{
next[i] = nullptr;
}
}
};
public:
TrieNode *root; //定义根结点
/** Initialize your data structure here. */
Trie() { //构造函数初始化根结点
root = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *tmp = root; //初始化tmp结点
for (char ch :word) //获取字符串中每一个字符
{
int index = ch - 'a'; //获取该字符的index
if (tmp->next[index] == nullptr) //如果没建立过通往该字符的路径
{
tmp->next[index] = new TrieNode(); //则建立
}
tmp = tmp->next[index]; //更新tmp
tmp->path++; //tmp的path++
}
tmp->end++; //已该结点结束 end++
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode *tmp = root;
for (char ch : word)
{
int index = ch - 'a';
if (tmp->next[index] == nullptr) //如果没有该路径，返回false
{
return false;
}
tmp = tmp->next[index];//更新tmp
}
if (tmp->end == 0) //如果没以该结点结束，说明该路径只是一个更长字符串的子串，返回false
{
return false;
}
return true;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode *tmp = root;
for (char ch : prefix)
{
int index = ch - 'a';
if (tmp->next[index] == nullptr)
{
return false;
}
tmp = tmp->next[index];
}
if (tmp->path == 0) //以字符串为前缀，只要求路径中有该字符串即可
{
return false;
}
return true;
}
bool delete(string word)
{
if(search(word)) //前缀树中有该字符串才能删除
{
TrieNode *tmp = root;
for(char ch:word)
{
int index=ch-'a';
tmp = tmp->next[index];
tmp->path--; //路径上的path--
}
tmp->end--; //路径结尾end--
return true;
}
else
return false;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
