poj 3630 Phone List

#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;
}