#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
int Trie[N][10];
int nodeN;
int main()
{
int t, n, i, j, isPrefix, flag;
char ph[15];
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
isPrefix=0;
nodeN=0;
memset(Trie[0], 0, sizeof(int)*10);
for(i=0; i<n; ++i)
{
scanf("%s", ph);
flag=0;
int cur=0;
if(!isPrefix)
for(j=0; ph[j]; ++j)
{
int k=ph[j]-'0';
if(!Trie[cur][k])
{
if(i!=0 && !flag)//利用第一个字符串建立一个初始的trie树
{
flag=1;//建立了新节点（如果当前 cur 节点还有孩子说明没有公共前缀， 否则说明当前路已经走到了尽头，产生了公共前缀）
int c;
for(c=0; c<10; ++c)//检查时候当前节点cur是否有孩子节点
if(Trie[cur][c])
break;
if(c>=10)
{
isPrefix=1; //没有孩子节点，则说明产生了公共前缀
break;
}
}
Trie[cur][k]=++nodeN;
memset(Trie[nodeN], 0, sizeof(int)*10);
}
cur=Trie[cur][k];
}
if(flag==0 && i!=0)//如果不是第一个字符串，而且在遍历整个树的时候没有发现建立新的节点，则说明当前字符串必然是之前某个字符串的公共前缀
isPrefix=1;
}
if(isPrefix)
printf("NO\n");
else printf("YES\n");
}
return 0;
}
/*
好不容易想用一下链表来写一下，还超时啊。。。。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
class Trie
{
public:
Trie *ch[10];
Trie()
{
memset(ch, 0, sizeof(ch));
}
};
int main()
{
int t, n, i, j, isPrefix, flag;
char ph[15];
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
Trie *root=new Trie();
isPrefix=0;
for(i=0; i<n; ++i)
{
scanf("%s", ph);
flag=0;
Trie * cur=root;
if(!isPrefix)
for(j=0; ph[j]; ++j)
{
int k=ph[j]-'0';
if(!cur->ch[k])
{
if(i!=0 && !flag)
{
flag=1;
int c;
for(c=0; c<10; ++c)
if(cur->ch[c])
break;
if(c>=10)
{
isPrefix=1;
break;
}
}
cur->ch[k]=new Trie();
}
cur=cur->ch[k];
}
if(flag==0 && i!=0)
isPrefix=1;
}
if(isPrefix)
printf("NO\n");
else printf("YES\n");
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3777106.html，如需转载请自行联系原作者
