首页 > 代码库 > poj 3630 Phone List (字典树 +静态字典树）

poj 3630 Phone List (字典树 +静态字典树）

2024-07-13 21:07:47   229人阅读

Phone List
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 22235 Accepted: 6885

Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let‘s say the phone catalogue listed these numbers:

  • Emergency 911
  • Alice 97 625 999
  • Bob 91 12 54 26

In this case, it‘s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob‘s phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output "YES" if the list is consistent, or "NO" otherwise.

Sample Input

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output

NO
YES

Source

Nordic 2007

字典树的一道经典题；话说做了这么多到字典树了，对字典树的思路应该还算比较清晰了，开始看到这道题，我的思路还是先建立字典树，在末尾加标志，判断字典树中间是否有标志，后来做着发现这种思路做不下去了；后来就换了种思路；这道题有两种情况，第一种是，先输入比较长的字符串，再输入较短的字符串，如果是这种情况，那么在这个过程中如果没有新节点说明较短的字符串就是长的字符串的一个前缀；第二种情况，先输入的是比较短的字符串，在输入较长的字符串，如果在这种情况下，读取到了较短字符串的结束标志，说明较短的字符串是较长字符串的一个前缀，其他的情况说明就不是公共前缀；

这道题在很多oj上都有，在hduoj 和 nyoj上直接用字典树就可以水过，在poj上用的是静态数组才可以过，用malloc分配的空间比较耗时；

下面是直接用字典树水过的代码；

#include <cstdlib>
#include <cstdio>
#include <cstring>
typedef struct node //节点的结构体
{
    int count;//计数，标志结束
    struct node * next[10];
}node;
node * newnode() //创建新节点
{
    node *q;
    q=(node*)malloc(sizeof(node));
    q->count=0;
    for(int i=0;i<10;i++)
        q->next[i]=NULL;
    return q;
}
int build(node *T,char *s) //建立字典树
{
   node *q;
   q=T;
   int i,k,tag,len;
   len=strlen(s);
   for(tag=i=0;i<len;i++)
   {
       k=s[i]-'0';
       if(q->next[k]==NULL)
       {
           q->next[k]=newnode();
           tag=1;  // 产生了新节点
       }
       q=q->next[k];
       if(q->count) //遇到了结束的节点
             return 0;
   }
   q->count=1; //标记结束的节点
   if(!tag)  return 0;
   return 1;
}
int del(node *p)  //释放字典树空间，否则占用空间太大
{
    if(p==NULL) return 0;
    for(int i=0;i<10;i++)
        if(p->next[i]) del(p->next[i]);
       free(p);
    return 0;
}
int main()
{
    //freopen("1.txt","r",stdin);
    node *T;
    int n,m,flag;
    char s[12];
    scanf("%d",&n);
    while(n--)
    {
        T=(node *)malloc(sizeof(node));//分配头节点
        T->count=0;
        for(int i=0;i<10;i++)
        T->next[i]=NULL;
        flag=1;
        scanf("%d",&m);
        for(int i=0;i<m;i++)
          {
              scanf("%s",s);
               if(flag)
                flag=build(T,s);
          }
          del(T);
          if(!flag)
            printf("NO\n");
          else
            printf("YES\n");
    }
    return 0;
}
开始用字典树写的时候我犯了一个很不应该的错误，我把头节点放在循环的外面，然后我提交总是wa，找了好久错误也没有找到，而且这样写导致我把del函数放在那个位置也出现了异常错误，后来，才明白过来，这道题是一组数据就相当于要建立一个字典树；这种错误不应该犯的！

下面是用静态数组写的，第一次用静态数组写字典树，参考了别人的代码；

#include <cstdlib>
#include <cstdio>
#include <cstring>
typedef struct node //节点的结构体
{
    bool end;//结束的标志
    int  a[10];
}node;
node phonelist[100000];
int x;
int flag;
void Init()
{
    flag=1;//标志
    x=0; //初始位置；
    for(int i=0;i<100000;i++)
    {
        phonelist[i].end=false;
        for(int j=0;j<10;j++)
            phonelist[i].a[j]=-1;
    }
}
int build(char *s) //建立字典树
{
    int k,now=0,tag=0;// 初始位置
    int len=strlen(s);
    for(int i=0;i<len;i++)
   {
       k=s[i]-'0';
       if(phonelist[now].a[k]==-1)
       {
           tag=1;//说明进入一个新的位置
           phonelist[now].a[k]=++x; //给数组赋值
           now=x;//下一个位置
       }
       else
       {
          now=phonelist[now].a[k];
          if(phonelist[now].end)
            return 0;  //单词的结束标志
       }
   }
   phonelist[now].end=true; //标记结束的节点
   if(!tag) return 0;
   return 1;
}
int main()
{
    //freopen("1.txt","r",stdin);
    int n,m;
    char s[12];
    scanf("%d",&n);
    while(n--)
    {
        Init();
        scanf("%d",&m);
        for(int i=0;i<m;i++)
          {
               scanf("%s",s);
               if(flag)
               flag=build(s);
          }
          if(flag)
            printf("YES\n");
          else
            printf("NO\n");
    }
    return 0;
}

总体的思路都是一样的，只不过写的方式不一样而已，这里我也犯了一个错误，我开始把结构体中的数组定义成了字符型了，我也找了好久错误都没找到,浪费了好久的时间，要减少犯这种低级错误，算法最重要的还是思想！锻炼自己的思维能力！！

这道题还可以用另一种方法做的，直接用快排将它们排序，进行比较；

下面的代码是别人写的，可以参考参考；

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
char phone[10000][11];
int cmp(const void* a,const void* b)
{
    return strcmp((char*)a,(char*)b);
}

int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int i,n;
        bool flag=false;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%s",phone[i]);
        }
        qsort(phone,n,sizeof(phone[0]),cmp);
        for(i=0;i<n-1;i++)
        {
            if(strncmp(phone[i],phone[i+1],strlen(phone[i]))==0)
            {
                flag=true;
                break;
            }
        }
        if(flag==false)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}


联系
我们