1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define N 100005
5 using namespace std;
6 int Trie[N][10];
7 int nodeN;
8 int main()
9 {
10 int t, n, i, j, isPrefix, flag;
11 char ph[15];
12 scanf("%d", &t);
13 while(t--)
14 {
15 scanf("%d", &n);
16 isPrefix=0;
17 nodeN=0;
18 memset(Trie[0], 0, sizeof(int)*10);
19 for(i=0; i<n; ++i)
20 {
21 scanf("%s", ph);
22 flag=0;
23 int cur=0;
24 if(!isPrefix)
25 for(j=0; ph[j]; ++j)
26 {
27 int k=ph[j]-'0';
28 if(!Trie[cur][k])
29 {
30 if(i!=0 && !flag)//利用第一个字符串建立一个初始的trie树
31 {
32 flag=1;//建立了新节点（如果当前 cur 节点还有孩子说明没有公共前缀， 否则说明当前路已经走到了尽头，产生了公共前缀）
33 int c;
34 for(c=0; c<10; ++c)//检查时候当前节点cur是否有孩子节点
35 if(Trie[cur][c])
36 break;
37 if(c>=10)
38 {
39 isPrefix=1; //没有孩子节点，则说明产生了公共前缀
40 break;
41 }
42 }
43 Trie[cur][k]=++nodeN;
44 memset(Trie[nodeN], 0, sizeof(int)*10);
45 }
46 cur=Trie[cur][k];
47 }
48 if(flag==0 && i!=0)//如果不是第一个字符串，而且在遍历整个树的时候没有发现建立新的节点，则说明当前字符串必然是之前某个字符串的公共前缀
49 isPrefix=1;
50 }
51 if(isPrefix)
52 printf("NO\n");
53 else printf("YES\n");
54 }
55 return 0;
56 }
/*
好不容易想用一下链表来写一下，还超时啊。。。。
*/
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 class Trie
6 {
7 public:
8 Trie *ch[10];
9 Trie()
10 {
11 memset(ch, 0, sizeof(ch));
12 }
13 };
14
15 int main()
16 {
17 int t, n, i, j, isPrefix, flag;
18 char ph[15];
19 scanf("%d", &t);
20 while(t--)
21 {
22 scanf("%d", &n);
23 Trie *root=new Trie();
24 isPrefix=0;
25 for(i=0; i<n; ++i)
26 {
27 scanf("%s", ph);
28 flag=0;
29 Trie * cur=root;
30 if(!isPrefix)
31 for(j=0; ph[j]; ++j)
32 {
33 int k=ph[j]-'0';
34 if(!cur->ch[k])
35 {
36 if(i!=0 && !flag)
37 {
38 flag=1;
39 int c;
40 for(c=0; c<10; ++c)
41 if(cur->ch[c])
42 break;
43 if(c>=10)
44 {
45 isPrefix=1;
46 break;
47 }
48 }
49 cur->ch[k]=new Trie();
50 }
51 cur=cur->ch[k];
52 }
53 if(flag==0 && i!=0)
54 isPrefix=1;
55 }
56 if(isPrefix)
57 printf("NO\n");
58 else printf("YES\n");
59 }
60 return 0;
61 }
