Phone List

思路：

Trie树。前缀可分为两种情况，一种是当前结点是某个字符串的前缀，另一种是某个字符串是当前字符串的前缀。每次插入时先判断新插入的结点是不是单词结点，如果是，就说明该字符串是当前字符串的前缀，直接跳出程序，输出NO。一个单词插入完成后判断该单词结点下有没有子结点，如果有，就说明当前字符串是某个字符串的前缀，跳出程序，输出NO。如果所有字符串插入完毕却没有跳出，就输出YES。

 1 #define maxnode 100000
 2 #define sigma_size 10
 3 #include<cstdio>
 4 #include<cstring>
 5 bool ans;
 6 struct Trie {
 7     int ch[maxnode][sigma_size];
 8     int val[maxnode];
 9     int sz;
10     int idx(char c) {
11         return c-'0';
12     }
13     void insert(char *s) {
14         int u=0,n=strlen(s);
15         for(int i=0;i<n;i++) {
16             int c=idx(s[i]);
17             if(!ch[u][c]) {
18                 memset(ch[sz],0,sizeof(ch[sz]));
19                 val[sz]=0;//visited
20                 ch[u][c]=sz++;
21             }
22             if(val[u]==1) {
23                 ans=true;
24                 return;
25             }
26             u=ch[u][c];
27         }
28         /*if(val[u]==0) {
29             ans=true;
30             return;
31         }*/
32         val[u]=1;
33         for(int i=0;i<sigma_size;i++) {
34             if(ch[u][i]) {
35                 ans=true;
36                 return;
37             }
38         }
39     }
40 };
41 Trie trie;
42 int main() {
43     int t;
44     scanf("%d",&t);
45     while(t--) {
46         int n;
47         scanf("%d",&n);
48         ans=false;
49         memset(&trie,0,sizeof(trie));
50         trie.sz=1;
51         memset(trie.ch[0],0,sizeof(trie.ch[0]));
52         while(n--) {
53             char s[10];
54             scanf("%s",s);
55             trie.insert(s);
56         }
57         printf(ans?"NO
":"YES
");
58     }
59     return 0;
60 }

注：本随笔整理自QQ空间旧文。发布时间为2017年3月14日。

查看原文