A38145. 电话号码给你一些电话号码，请判断它们是否是一致的，即是否有某个电话是另一个电话的前缀。比如：Emergency 911Alice 97 625 999Bob 91 12 54 26在这个例子中，我们不可能拨通Bob的电话，因为Emergency的电话是它的前缀，当拨打Bob的电话时会先接通Emergency，所以这些电话号码不是一致的。输入第一行是一个整数t，1 ≤ t ≤ 40，表示测试数据的…
填空题
困难
知识点
题目描述
电话号码
给你一些电话号码，请判断它们是否是一致的，即是否有某个电话是另一个电话的前缀。比如：
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
在这个例子中，我们不可能拨通Bob的电话，因为Emergency的电话是它的前缀，当拨打Bob的电话时会先接通Emergency，所以这些电话号码不是一致的。
输入
第一行是一个整数t，1 ≤ t ≤ 40，表示测试数据的数目。 每个测试样例的第一行是一个整数n，1 ≤ n ≤ 10000，其后n行每行是一个不超过10位的电话号码。
输出
对于每个测试数据，如果是一致的输出“YES”，如果不是输出“NO”。
样例输入
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
样例输出
NO
YES
参考答案
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int t, n, flag;
struct data {
char str[11];
}
d[10010];
struct tree {
char val;
bool tail;
tree *son[10];
tree() {
tail = false;
for (int i=0;i<10;i++)
son[i] = NULL;
}
}
;
void insert(tree *&root,char *a) {
int len = strlen(a);
tree *t = new tree;
t = root;
if(root == NULL) {
root = new tree;
//新建头结点
}
for (int i=0;i<len;i++) {
if(t->son[a[i]-'0'])//有重合 {
if(t->son[a[i]-'0']->tail)
flag = 1;
} else {
tree *temp = new tree;
temp->val = a[i];
t->son[a[i]-'0'] = temp;
}
t = t->son[a[i]-'0'];
if(i == len-1)//这是某个电话号码的最后一位
t->tail = true;
}
}
bool cmp(data a,data b) {
return strcmp(a.str,b.str)<0;
}
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
tree *root = new tree;
flag = 0;
//判断是否有重合的
for (int i=0;i<n;i++)
scanf("%s",&d[i].str);
sort(d,d+n,cmp);
for (int i=0;i<n;i++) {
insert(root,d[i].str);
}
if(flag)
printf("NO\n"); else
printf("YES\n");
}
return 0;
}
上一题
下一题