题目描述

给出一个电话列表，如果列表中存在其中一个号码是另一个号码的前缀这一情况，那么就称这个电话列表是不兼容的。

假设电话列表如下：

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

在此例中，报警电话号码（911）为Bob电话号码（91 12 54 26）的前缀，所以该列表不兼容。

输入格式
第一行输入整数t，表示测试用例数量。

对于每个测试用例，第一行输入整数n，表示电话号码数量。

接下来n行，每行输入一个电话号码，号码内数字之间无空格，电话号码不超过10位。

输出格式
对于每个测试用例，如果电话列表兼容，则输出”YES”。

否则，输出”NO”。

数据范围
1≤t≤40,
1≤n≤10000
输入样例：
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
输出样例：
NO
YES

trie基本操作
给出 N 个字符串，看是否有一个串 A 为串 B 的前缀。

因为我们在Trie树插入操作中已经对每一串字符串都打上了标记，
所以满足答案的关系只有两种，
一种是插入的串是之前的串的前缀，那么只要看在插入过程中是不是没有新增节点；
另一种是插入的串包括之前的串，也就是之前的串是插入的串的前缀，这个只要看看有没有走到打了标记的点就好了。
所以只需要在插入时判断即可；

请不要忘记清空trie

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int T,n,m,idx,ans=0,trie[100050][25],cnt[100050];
char str[25];

template<typename T>inline void read(T &x)
{
    x=0;T f=1,ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
}

inline void clear() {
    for(int i=0;i<=idx;i++) {
        for(int j=0;j<=15;j++) {
            trie[i][j]=0,cnt[i]=0;
        }
    }
}

inline int insert(char str[]) {
    int p=0,l=strlen(str+1);
    int f1=0,f2=1;
    for(int i=1;i<=l;i++) {
        int ch=str[i]-'0';
        if(!trie[p][ch]) trie[p][ch]=++idx,f2=0;
        p=trie[p][ch];
        if(cnt[p]) f1=1;
    }
    cnt[p]=1;
    if(f1) return 1;
    if(f2) return 1;
    return 0;
}

int main() {
    read(T);
    while(T--) {
        clear();
        ans=0;idx=0;
        read(n);
        for(int i=1;i<=n;i++) {
            scanf("%s",str+1);
            if(insert(str)) ans=1;
        }
        if(ans) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}