首页 > 代码库 > poj4089:电话号码

poj4089:电话号码

总时间限制: 1000ms 内存限制: 65536kB描述给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:Emergency 911Alice 97 625 999Bob 91 12 54 26在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。输入第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。输出对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。样例输入2391197625999911254265113123401234401234598346样例输出NOYES

 

这题思路很简单,就是字母树,俗称trie树。然后我就开始傻乎乎地写了。。。果不其然地WA了。

忘记注意一件事情,正常的trie树只是判断前缀,这个还要判断后缀。

即如果输入顺序是:

11

110

需要判断出来NO。

而且,如果输入顺序是:

110

11

也需要判断出来是NO。

注意到这一点就很简单了。

直接看代码:

 1 #include <iostream> 2 #include <stdio.h> 3  4 using namespace std; 5  6 struct P 7 { 8     //int i; 9     P* next[10];10     bool flag;11 }s;12 13 void init()14 {15     s.flag = false;16     //s.i = -1;17     for(int i = 0; i < 10; i ++)18         (s.next)[i] = NULL;19 }20 char a[11];21 bool add(int i,P* p)22 {23     if(p->flag == true)24         return false;25     if(a[i] == \0)26     {27         p->flag = true;28         bool f = true;29         for(int j = 0; j < 10; j ++)30             if((p->next)[j] !=NULL)31                 f = false;32         return f;33     }34     int x = a[i]-0;35     if((p->next)[x] == NULL)36     {37         (p->next)[x] = new P();38         (p->next)[x]->flag = false;39         for(int j = 0; j < 10; j ++)40         {41             (((p->next)[x])->next)[j] = NULL;42         }43     }44     if(add(i+1,(p->next)[x]))45         return true;46     return false;47 }48 49 int main()50 {51     int t;52     scanf("%d",&t);53     while(t--)54     {55         init();56         int n;57         scanf("%d",&n);58         bool f=true;59         char c;60         scanf("%c",&c);61         while(n--)62         {63             cin.getline(a,11);64             if(!add(0,&s))65                 f = false;66         }67         if(f)68             cout<<"YES"<<endl;69         else70             cout<<"NO"<<endl;71     }72     return 0;73 }