题目描述

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

假设电话列表如下：

·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

Hash

在这里向大家提供一种除了字典树之外的解法，也就是直接利用Hash。
将每个电话号码都看成一个字符串，对于一个字符串a，如果它是某个字符串b的前缀，那么整个字符串a的Hash值一定会在b中出现，所以，对于每一个字符串，我们在从头到尾计算这个字符串的Hash值的时候，把每个前缀的Hash值都存下来，而对于整个字符串的Hash值，先判断一下它是否出现过，如果出现过，说明不安全，则直接输出NO即可，如果没有出现过，则将这个Hash值也存下来，再用相同的过程来判断下一个电话号码。
为了方便判定，我们将读入的字符串排个序，然后从大到小进行上述过程。这样就可以保证如果存在一个字符串a是字符串b的前缀，那么在判断a之前一定已经存完了b的所有前缀的Hash值。也就是说，在判断一个电话号码时，不再需要考虑这个字符串的前缀是否是另一个电话号码，因为如果存在这种情况，那一定会在接下来遍历电话号码的过程中被判断。

C++ 代码

# include <iostream>
# include <string>
# include <unordered_set>
# include <algorithm>

using namespace std;

typedef unsigned long long ULL;
const int maxn = 1e4 + 5, Hash = 131;
string phone[maxn];
ULL h[maxn];
unordered_set<ULL> F;

bool check(string &number)
{
    for (int i = 0; i < number.size(); i++) {
        h[i + 1] = h[i] * Hash + number[i] - '0' + 1;  // + 1 为了防止 012  与  12 这种情况
        if (i + 1 == number.size() && F.count(h[i + 1]))
            return true;
        F.insert(h[i + 1]);
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        F.clear();
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> phone[i];
        sort(phone + 1, phone + n + 1);
        bool success = true;
        for (int i = n; i; i--) {
            if (check(phone[i])) {
                success = false;
                break;
            }
        }
        if (success)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

对于字典树的做法，这里就不细讲了，毕竟yxc老师课上讲的就是字典树，况且秦淮岸大佬也写了一个字典树的题解，这里就把我写的字典树代码奉上，各位也可以参考一下。

C++ 代码

# include <iostream>
# include <string>
# include <cstring>
# include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;
int F[maxn][10], pos;
bool e[maxn];

bool insert(string &s)
{
    int p = 0;
    bool pre_of_other = true, have_pre = false;
    for (int i = 0; i < s.size(); i++) {
        if (!F[p][s[i] - '0']) {
            pre_of_other = false;
            F[p][s[i] - '0'] = ++pos;
        }
        p = F[p][s[i] - '0'];
        if (e[p])
            have_pre = true;
    }
    e[p] = true;
    return !pre_of_other && !have_pre;
}

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        memset(F, 0, sizeof F);
        memset(e, false, sizeof e);
        pos = 0;
        int n;
        cin >> n;
        bool success = true;
        while (n--) {
            string s;
            cin >> s;
            if (!insert(s))
                success = false;
        }
        if (success)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}