UVA11362 Phone List 题解

题目链接：UVA11362 Phone List

题意：给定$n$个长度不超过$10$的数字串，判断是否有两个字符串$A$和$B$,满足$A$是$B$的前缀，若有，输出NO，若没有，输出YES。

其实可以去建个 $\tt{trie}$ 树然后dfs的

但是方便起见，直接sort就能过

时间复杂度 $O(Qn^2)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e4+15)

int Q,n;
string s[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> Q;
    while(Q--)
    {
        cin >> n;
        for(int i=1; i<=n; i++)
            cin >> s[i];
        sort(s+1,s+1+n);
        int ok=0;
        for(int i=2; i<=n&&!ok; i++)
            if(s[i].find(s[i-1])==0)ok=1;
        cout << (ok?"NO\n":"YES\n");
    }
    return 0;
}