AcWing 161. 电话列表
原题链接
简单
作者:
周哲宇
,
2024-10-25 11:04:53
,
所有人可见
,
阅读 1
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int son[N][10], cnt[N], idx = 0;
void insert(string str){
int p = 0;
for (int i = 0; i < str.length(); i ++){
int u = str[i] - '0';
if (! son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++;
}
int query(string str){
int p = 0;
for (int i = 0; i < str.length(); i ++){
int u = str[i] - '0';
if (cnt[p]) return 1;
p = son[p][u];
}
if (cnt[p] >= 2) return 1;
return 0;
}
int main(){
int t, n;
scanf("%d", &t);
while (t--){
int n, flag = 0;
scanf("%d", &n);
memset(cnt, 0, sizeof cnt);
memset(son, 0, sizeof son);
idx = 0;
string str[N];
for (int i = 1; i <= n; i ++){
cin >> str[i];
insert(str[i]);
}
for (int i = 1; i <= n; i ++){
if (query(str[i])) {
flag = 1;
break;
}
}
cout<<(flag ? "NO": "YES")<<endl;
}
}