题解 UVA11362 【Phone List】
swiftc
2019-09-01 19:28:17
一道很简单的字典树模版题
__字典树是什么?__
简单的说，字典树就是把很多个字符串合并在一起，如下图一样的树，详细建立的方法可以看我的代码
我们把所有的电话号码建成一颗字典书，在插入的过程住如果发现有结束标记，或者结束时发现这个节点还有儿子，就输出$NO$，如果没有发现这种情况就输出$YES$
__代码：__
```cpp
#include<bits/stdc++.h>
using namespace std;
int cnt;
struct trie{
int son[10],end=0;
}a[1000001];
int main(){
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++){
memset(a,0,sizeof(a));
int n;
cnt=0;
scanf("%d",&n);
bool flag=0;
for(int j=1;j<=n;j++){
string s;
cin>>s;
int now=0;
for(int k=1;k<=s.length();k++){
if(a[now].son[s[k-1]-'0']){
now=a[now].son[s[k-1]-'0'];
}
else{
a[now].son[s[k-1]-'0']=++cnt;
now=cnt;
}
if(a[now].end==1){
flag=1;
}
if(k==s.length()){
for(int i=0;i<=9;i++){
if(a[now].son[i])flag=1;
}
a[now].end=1;
}
}
}
if(flag){
puts("NO");
}
else{
puts("YES");
}
}
return 0;
}
```