首页 > 代码库 > poj 3630 Phone List

poj 3630 Phone List

2024-07-07 14:58:40   220人阅读

 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 }

 

 


联系
我们