Example
有如下单词
1.abacb 2.abc 3.acb 4.aaa 5.bcb
构建字典树如下图
例题
第一种解法
#include<iostream>
#define ll long long
struct Node{
Node *son[10]={NULL};
//isend 是否为单词结尾
bool isend=false;
};
void buildtrie(Node *root,std::string s,bool &isPre){
Node *temp=root;
for(int i=0;i<s.size();i++){
int ch=s[i]-'0';//变为数字
if(temp->son[ch]==NULL){
Node *newNode=new Node;
//父结点指向孩子节点
temp->son[ch]=newNode;
}
//已经找到了答案
else if(i==s.size()-1){
isPre=true;
return;
}
//下一次从s[i]的节点去找
temp=temp->son[ch];
if(temp->isend){
isPre=true;
return;
}
}
//标记:已经到了终点
temp->isend=true;
}
int t,n;
std::string s;
int main(){
std::cin>>t;
Node *root;
while(t--){
root=new Node;
std::cin>>n;
// isPre 是否存在两个数字串 S,T，使得 S 是 T 的前缀
bool isPre=false;
while(n--){
std::cin>>s;
if(!isPre)buildtrie(root,s,isPre);
}
if(isPre)std::cout<<"NO\n";
else std::cout<<"YES\n";
}
}
提交上去会内存超限，这是因为每一次建字典树时，之前的所有信息全部都还有，故我们要写一个 deleteTrie 函数，来递归的删除。
#include<iostream>
#define ll long long
struct Node{
Node *son[10]={NULL};
//isend 是否为单词结尾
bool isend=false;
};
void buildtrie(Node *root,std::string s,bool &isPre){
Node *temp=root;
for(int i=0;i<s.size();i++){
int ch=s[i]-'0';//变为数字
if(temp->son[ch]==NULL){
Node *newNode=new Node;
//父结点指向孩子节点
temp->son[ch]=newNode;
}
//已经找到了答案
else if(i==s.size()-1){
isPre=true;
return;
}
//下一次从s[i]的节点去找
temp=temp->son[ch];
if(temp->isend){
isPre=true;
return;
}
}
//标记:已经到了终点
temp->isend=true;
}
void deleteTrie(Node *root){
if(!root)return;
for(int i=0;i<10;i++)
deleteTrie(root->son[i]);
delete root;
}
int t,n;
std::string s;
int main(){
std::cin>>t;
while(t--){
Node *root=new Node;
std::cin>>n;
// isPre 是否存在两个数字串 S,T，使得 S 是 T 的前缀
bool isPre=false;
while(n--){
std::cin>>s;
if(!isPre)buildtrie(root,s,isPre);
}
if(isPre)std::cout<<"NO\n";
else std::cout<<"YES\n";
deleteTrie(root);
}
}
这样就可以 AC 了。