题目描述

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

假设电话列表如下：

·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

算法1

(Trie) $O(n)$

利用Trie树求前缀，每个打标记。

时间复杂度

$O(n)$
都是看着视频打的。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, idx, son[N][10];
char str[20];
bool flag[N];
bool add(char *str)
{
    int p = 0;
    bool fa = false, fb = false;
    for(int i = 0; str[i]; i ++)
    {
        int u = str[i] - '0';
        if(!son[p][u])
        {
            son[p][u] = ++ idx;
            fb = true;
        }
        p = son[p][u];
        if(flag[p]) fa = true; 
    }
    flag[p] = true;
    return fb && !fa;
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n;
        memset(son, 0, sizeof son);
        memset(flag, false, sizeof flag);
        idx = 0;
        bool res = true;
        for(int i = 0; i < n; i ++)
        {
            cin >> str;
            if(!add(str)) res = false;
        }
        if(res) puts("YES");
        else puts("NO");
    }
    return 0;
}