电话列表（字典树）------------Five-菜鸟级
电话列表（字典树）------------Five-菜鸟级
Fivecc
发布于 2022-11-21 15:44:40
发布于 2022-11-21 15:44:40
电话列表 时限：1000 MS 内存限制：65536K 提交材料共计：34731 接受： 9962 描述 给定一个电话号码列表，确定它是否一致，因为没有号码是另一个号码的前缀。假设电话目录列出了这些号码：
- 紧急911
- 爱丽丝97 625 999
- 鲍勃91 12 54 26
在这种情况下，不可能打电话给Bob，因为一旦您拨了Bob电话号码的前三位数，中央就会将您的电话直接打到紧急线路。所以这个名单就不一致了。 输入 输入的第一行给出一个整数，1≤t≤40，测试用例的数量。每个测试用例从n，电话号码，在一条单独的线路上，1≤。n≤10000。然后：n每行上有一个唯一电话号码的线路。电话号码最多是十位数。 输出量 对于每个测试用例，如果列表一致，输出“是”，否则输出“否”。 样本输入 2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 样本输出 NO YES
题目链接：http://poj.org/problem?id=3630
题解： 这是trie(字典)树模板题，字典树插入操作的运用，插入一个单词是 在单词最后一个字符打上结束标记。插入新单词时，不会遇到单词结束标记，则不会起冲突 满足条件。
想了解 字典树（点击即可）
AC代码：
#include<stdio.h>
#include<string.h>
#define N 60001
int trie[N][13];
int sum[N]; //存从根节点到单词（前缀）的单词数
int tot;
int flag;
void insert(char *s){//插入单词
if(flag) return;//已经冲突了 则不必插入单词了
int i,id,len,root=0; len=strlen(s);
for(i=0;i<len;i++)
{ id=s[i]-'0';
if(!trie[root][id])trie[root][id]=++tot;//给字符节点编号
root=trie[root][id]; //更新字符节点
if(sum[root]==-1){flag=1;return;}//如果遇到下一个字符节点为某单词结尾标记 -1 则不符合要求
sum[root]++;
}
if(sum[root]==1)sum[root]=-1;
//在满足不是前缀 单词最后一个字符为标记为 -1
else flag=1;
}
int main()
{ char s[12]; int T,n;
scanf("%d",&T);
while(T--){
memset(trie,0,sizeof(trie));
memset(sum,0,sizeof(sum));
flag=0;tot=0;
scanf("%d",&n);
while(n--)scanf("%s",&s),insert(s);//输入单词表
if(flag==1) printf("NO\n");
else printf("YES\n");
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读