首页 > 代码库 > Phone List

Phone List

2024-07-14 00:27:47   227人阅读

Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
Submit Status

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

2391197625999911254265113123401234401234598346

Sample Output

NOYES

 

 题目意思很清楚：就是判断输入的电话号码中是否有号码是其他号码的前缀，很显然要用到字典树。根据分析可知:
  如果字符串Xn=X1X2....Xn是字符串Ym=Y1Y2....Ym的前缀，有在插入的时候有两种情况:Xn在Yn之前插入，Xn在Yn之后插入。
  1)如果Xn在Yn之前插入，那么在插入Yn的时候必然经过Xn的路径，此时可以根据判断在这条路径上是否已经有结点被标记已经构成完成的字符串序列来判断是否存在Yn的前缀；
  2)如果Xn在Yn之后插入，那么插入完成之后当前指针指向的结点的next数组中的元素必定不全为NULL。
代码：
#include<stdio.h>#include<stdlib.h>#define MAX 10using namespace std;bool flag;typedef struct Trie_Node{    bool isphone;    struct Trie_Node *next[MAX];}Trie;void insert(Trie *root,char *phone)//插入 {    Trie *p=root;    while(*phone!=‘\0‘)    {        if(p->next[*phone-48]==NULL)        {            Trie *temp=(Trie *)malloc(sizeof(Trie));            temp->isphone=false;            for(int i=0;i<MAX;i++)            {                temp->next[i]=NULL;            }            p->next[*phone-48]=temp;        }        if(p->isphone==true)            flag=true;        p=p->next[*phone-48];        phone++;    }    p->isphone=true;    for(int i=0;i<MAX;i++)    {        if(p->next[i]!=NULL)        {            flag=true;            break;        }    }}void del(Trie *root)//删除 {    for(int i=0;i<MAX;i++)    {        if(root->next[i]!=NULL)        {            del(root->next[i]);        }    }    free(root);}int main(int argc,char *argv[]){    int t;    scanf("%d",&t);    while(t--)    {        int i;        int n;        char phone[11];        Trie *root=(Trie *)malloc(sizeof(Trie));        root->isphone=false;        flag=false;        for(i=0;i<MAX;i++)        {            root->next[i]=NULL;        }        scanf("%d",&n);        for(i=0;i<n;i++)        {            scanf("%s",phone);            if(flag!=true)            {                insert(root,phone);            }        }        if(flag==true)          printf("NO\n");        else          printf("YES\n");        del(root);    }    return 0;}

又一代码：

#include<stdio.h>#include<string.h>#include<stdlib.h>struct telnumber{    struct telnumber *child[10];    bool isroot;};struct telnumber *root;void initial(struct telnumber *node){    int i;    for(i=0;i<10;i++)        node->child[i]=NULL;    node->isroot=0;}void freedom(struct telnumber *p){ int i; for(i=0;i<10;i++)  if(p->child[i]!=NULL) freedom(p->child[i]); free(p);}bool insert(char *source){    int i,len; bool preinsert,postinsert;     struct telnumber *curent,*newnode; preinsert=postinsert=0; len=strlen(source); curent=root;    for(i=0;i<len;i++)    {        if(curent->child[source[i]-‘0‘]!=NULL)        {            curent=curent->child[source[i]-‘0‘];            if(curent->isroot==1) preinsert=1;        }        else//如果前缀在后面插入，则没有新节点申请        {            newnode=(struct telnumber *)malloc(sizeof(struct telnumber));            initial(newnode);            curent->child[source[i]-‘0‘]=newnode;            curent=newnode;            postinsert=1;//表示申请过新节点，第二种情况不可能发生了        }    }    curent->isroot=1;    if(preinsert||!postinsert) return 0;//返回0表示有前缀发生    else return 1;//无前缀发生} int main(){    int T,n,i;    bool flag;    char table[12];    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        root=(struct telnumber *)malloc(sizeof(struct telnumber));        initial(root);        for(i=0,flag=1;i<n;i++)        {            scanf("%s",table);            if(insert(table)==0) flag=0;        }        if(flag==1) printf("YES\n");        else printf("NO\n");        freedom(root);    }    return 0;}

 

另一种思路，就是先对电话号码序列进行排序，然后判断相邻的两个号码是否符合条件即可。这种思路利用了一种性质：

存在若干个字符串序列，对于两个字符串序列X[1....n]，Y[1....m]，如果X是Y的前缀，则在对所有的字符串序列按字典顺序排序后，
X[1..n]和Y[1....m]在位置上必然是直接相邻或者间接相邻的。间接相邻指存在字符串序列Z[1....t]，使得X是Z的前缀(X和Z直接相邻)，Z是Y的前缀(Z和Y直接相邻)，则X和Y也被认为是相邻的。下面证明这条性质:
假设X[1...n]是Y[1....m]的前缀，但是X和Y不相邻，即至少在X和Y之间存在一字符串序列Z[1....t]，其中X不是Z的前缀，Z也不是Y的前缀，且字典顺序为X<Z<Y。
证明：
 X不是Z的前缀，并且Z的字典顺序比X大，那么只存在两种情况:
  1)n>=t，这种情况下，必定存在一个i(0<=i<=t)使得X[i]<Z[i]，而由假设可知X是Y的前缀，则必有X[i]=Y[i]，此时Y的字典顺序小于Z，与条件不符，不成立。
  2)n<t，这种情况下，有两种可能，一种是对于所有的i(0<=i<=n)，X[i]=Z[i]，但是如此一来X是Z的前缀，与条件不符，不成立；
     另一种可能是存在i(0<=i<=n)，使得X[i]<Z[i]，与1)中所述情况一样，与条件不符，不成立。
因此假设不成立，从而性质得证。
因此可以利用此性质解决这道题目，题目只需判断是否存在一个号码是否是另一个号码的前缀即可。所以可以先对所有的号码序列进行字典排序，然后判断直接相邻的两个号码是否符号条件即可。如果所有直接相邻的号码都不存在一个号码是另一个号码的前缀，那么这些号码序列中肯定不存在一个号码是另一个号码的前缀。
代码：
#include<iostream>#include<algorithm>#include<cstring>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;}


            @@@@if(strncmp(phone[i],phone[i+1],strlen(phone[i]))==0)//比较字符串的前strlen长度的字符
字典树！新番字典树第一弹，主要是套模板，在建树过程中对每个号码的尾部进行标记，每输入一个号码分两种情况讨论，如果这个号码是之前输入的某个号码的前缀，或者这个号码的前缀是之前输入的某个号码，均不符合要求，输出NO，否则输出YES。注意每组判断输出完毕后释放这个Trie树的空间，再重新构建树，否则会MLE。

 

字典树：

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高

它有3个基本性质：

 

根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。
其基本操作有：查找、插入和删除,当然删除操作比较少见。我在这里只是实现了对整个树的删除操作,至于单个word的删除操作也很简单。

3编辑

搜索字典项目的方法为：
(1) 从根结点开始一次搜索；
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
其他操作类似处理
作用：

    串的快速检索

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

“串”排序

给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出
用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

最长公共前缀

对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先问题（以后补上）。
基本模板！！！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#defineMAX26//字符集大小
typedefstructTrieNode
{
intnCount;//记录该字符出现次数
structTrieNode*next[MAX];
}TrieNode;
 
TrieNodeMemory[1000000];
intallocp=0;
 
/*初始化*/
voidInitTrieRoot(TrieNode**pRoot)
{
*pRoot=NULL;
}
 
/*创建新结点*/
TrieNode*CreateTrieNode()
{
inti;
TrieNode*p;
p=&Memory[allocp++];
p->nCount=1;
for(i=0;i<MAX;i++)
{
p->next[i]=NULL;
}
returnp;
}
 
/*插入*/
voidInsertTrie(TrieNode**pRoot,char*s)
{
inti,k;
TrieNode*p;
if(!(p=*pRoot))
{
p=*pRoot=CreateTrieNode();
}
i=0;
while(s[i])
{
k=s[i++]-‘a‘;//确定branch
if(p->next[k])
p->next[k]->nCount++;
else
p->next[k]=CreateTrieNode();
p=p->next[k];
}
}
 
//查找
intSearchTrie(TrieNode**pRoot,char*s)
{
TrieNode*p;
inti,k;
if(!(p==*pRoot))
{
return0;
}
i=0;
while(s[i])
{
k=s[i++]-‘a‘;
if(p->next[k]==NULL)return0;
p=p->next[k];
}
returnp->nCount;
}
 

 

 


联系
我们