方法一：数组实现
1.解题思路
题意：
构建一颗字典树，满足基本插入，删除，查找字符串，查找前缀出现次数的操作。
相关知识点介绍：
- 字典树概念：又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
- 字典树基本性质：
- 根结点不包含字符，除根结点外每一个结点都只包含一个字符；
- 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串；
- 每个结点的所有子结点包含的字符都不相同。
- 字典树基本操作：
- 插入
- 删除
- 查找
- 字典树的应用：
- 串的快速检索
- “串”排序：数组的方式创建字典树，这棵树的每个结点的所有儿子显然地按照其字母大小排序。对这棵树进行先序遍历即可。
- 最长公共前缀：对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先问题。
2.解法
我们先尝试采用数组的方式构建字典树，这里我把所有数组封装成类，不过运行速度相比不封装时速度慢了。
- 用到的一些数组：
- trie[MAXN][26]：trie[i][c]表示i号点所连、存储字符为c+'a'的点的编号。
- child[MAXN]：child[i]表示i号结点的孩子数
- end[MAXN]：end[i]表示i号结点是一个字符串的终点
在字典树中插入一个字符串：对每个字符串从根结点出发开始对比，通过循环trie数组遍历字符串中每个字符，同时用child数组值自增1标记已遍历串的前缀数加1，对从根结点深度搜索下来的序列中未出现的字符，新建结点，到达字符串的最后一个字符的时候用end数组标记到了串尾。
在字典树中删除一个字符串：大致步骤同插入，从根结点开始向下遍历，同时用child数组值自减1标记已遍历串的前缀数少1，到达串尾的时候删除串尾标记end
在字典树中搜索一个字符串：大致步骤同插入，从根结点开始向下遍历，到达串尾的时候返回串尾标记end
在字典树中搜索一个字符串前缀数：大致步骤同插入，从根结点开始向下遍历，到达前缀尾的时候返回前缀的child标记，即以此为前缀的字符串数。
3.具体代码
const int MAXN=101000;//
class Trie{
private:
int trie[MAXN][26];//
int child[MAXN];//child[i]表示i号结点的孩子数
int end[MAXN];//end[i]表示i号结点是一个字符串的终点
int cn;//结点编号
public:
Trie(){
memset(trie,0,sizeof(trie));
memset(child,0,sizeof(child));
memset(end,0,sizeof(end));
cn=0;
}
void insert(string str){
int cur=0;
for(int i=0;i<str.size();i++){//从根结点开始向下遍历
char temp=str[i];
if(!trie[cur][temp-'a']){//从当前结点往下未找到该结点，则新建结点
cn++;
trie[cur][temp-'a']=cn;
}
cur=trie[cur][temp-'a'];
child[cur]++;//当前遍历序列的前缀数++
}
end[cur]++;//到字符串尾，做标记
}
void delete2(string str){
int cur=0;
for(int i=0;i<str.size();i++){//从根结点开始向下遍历
char temp=str[i];
cur=trie[cur][temp-'a'];
child[cur]--;当前遍历序列的前缀数--
}
end[cur]--;//到字符串尾，删除标记
}
bool search(string str){
int cur=0;
for(int i=0;i<str.size();i++){//从根结点开始向下遍历
char temp=str[i];
if(!trie[cur][temp-'a'])return false;//不存在该子结点，即不存在该单词/前缀
cur=trie[cur][temp-'a'];
}
return end[cur];//到字符串尾，返回标记
}
int prefixNumber(string str){
int cur=0;
for(int i=0;i<str.size();i++){//从根结点开始向下遍历
char temp=str[i];
if(!trie[cur][temp-'a'])return false;//不存在该子结点，即不存在该单词/前缀
cur=trie[cur][temp-'a'];
}
return child[cur];//到字符串尾，返回以次字符串的前缀数
}
};
class Solution {
public:
Trie trie;
vector<string> trieU(vector<vector<string> >& operators) {
vector<string>ans;
for(auto i :operators){
string a=i[0],b=i[1];
if(a=="1"){//插入操作
trie.insert(b);
}else if(a=="2"){//删除操作
trie.delete2(b);
}else if(a=="3"){//查找字符串
if(trie.search(b))ans.push_back("YES");
else ans.push_back("NO");
}else if(a=="4"){//查找前缀数
string t=to_string(trie.prefixNumber(b));
ans.push_back(t);
}
}
return ans;
}
};4.时间复杂度和空间复杂度分析
时间复杂度：，m为插入字符串的长度，每次对字典树增删改查的时间复杂度为
。
空间复杂度：,用到了二维数组trie，m是总的结点数，n是组成单词的字母数，这里n是26。
方法二：Node结点
1.解题思路
与数组实现方式类似，将数组实现改为构造字典树结点实现，优点是可以最大限度的利用空间。
2.解法
在字典树中插入一个字符串：对每个字符串从根结点出发开始对比（根结点不存放字符），通过next指针遍历字符串中每个字符，同时用child自增1标记已遍历串的前缀数加1，对从根结点深度搜索下来的序列中未出现的字符，新建结点，到达字符串的最后一个字符的时候用end标记到了串尾。
在字典树中删除一个字符串：大致步骤同插入，从根结点开始向下遍历，同时各个字串前缀数减一，到达串尾的时候删除串尾标记end
在字典树中搜索一个字符串：大致步骤同插入，从根结点开始向下遍历，到达串尾的时候返回串尾标记end
在字典树中搜索一个字符串前缀数：大致步骤同插入，从根结点开始向下遍历，到达前缀尾的时候返回前缀的child标记，即以此为前缀的字符串数。
3.图解
4.具体代码
class TrieNode{
public:
int end=0;//end表示结点是一个字符串的终点
int child;//child表示结点的孩子数
unordered_map<char,TrieNode*>next;//map表示该结点的孩子 字符值，指向该孩子的指针
TrieNode(){//无参的构造函数
end=0;
child=0;
}
~TrieNode(){//析构函数释放资源
for(auto i:next)
delete i.second;
}
};
class Trie{
protected:
TrieNode* root;
public:
Trie(){
root=new TrieNode();
}
void insert(string str){
TrieNode* cur=root;
root->child++;
for(auto i:str){//从根结点开始向下遍历
auto p_next=cur->next.find(i);//下一个子结点 cur->next是一个map，存放所有孩子
if(p_next==cur->next.end()){//
cur->next[i]=new TrieNode();
}
cur=cur->next[i];
cur->child++;//新建结点，孩子数++
}
cur->end++;
}
void delete2(string str){
TrieNode* cur=root;
root->child--;
for(auto i:str){//从根结点开始向下遍历
cur=cur->next[i];
cur->child--;//删除结点，孩子数--
}
cur->end--;
}
bool search(string str){
TrieNode* cur=root;
for(auto i:str){//从根结点开始向下遍历
auto p_next=cur->next.find(i);//下一个子结点 cur->next是一个map，存放所有孩子
if(p_next==cur->next.end())return 0;//不存在该子结点，即不存在该单词/前缀
cur=cur->next[i];
}
return cur->end;
}
int prefixNumber(string str){
TrieNode* cur=root;
for(auto i:str){//从根结点开始向下遍历
auto p_next=cur->next.find(i);//下一个子结点 cur->next是一个map，存放所有孩子
if(p_next==cur->next.end())return 0;//不存在该子结点，即不存在该单词/前缀
cur=cur->next[i];
}
return cur->child;
}
};
class Solution {
public:
Trie trie;
vector<string> trieU(vector<vector<string> >& operators) {
vector<string>ans;
for(auto i :operators){
if(i[0]=="1"){//插入操作
trie.insert(i[1]);
}else if(i[0]=="2"){//删除操作
trie.delete2(i[1]);
}else if(i[0]=="3"){//查找字符串
if(trie.search(i[1]))ans.push_back("YES");
else ans.push_back("NO");
}else if(i[0]=="4"){//查找前缀数
string t=to_string(trie.prefixNumber(i[1]));
ans.push_back(t);
}
}
return ans;
}
};5.时间复杂度和空间复杂度分析
时间复杂度：，n是字符串长度，每次增删改查的时间复杂度为
。
空间复杂度：，n是总的字符串长度，也即结点数。
京公网安备 11010502036488号