andyli

题解 SP4033 【PHONELST - Phone List】
考虑将所有的字符串构成一棵$Trie$,在构建过程中可以顺便判断答案。若当前串插入后没有新建任何结点,则当前串肯定...
扫描右侧二维码阅读全文
22
2019/06

题解 SP4033 【PHONELST - Phone List】

考虑将所有的字符串构成一棵$Trie$,在构建过程中可以顺便判断答案。若当前串插入后没有新建任何结点,则当前串肯定是之前插入的某个串的前缀;若插入过程中,有某个经过的结点带有串结尾标记,则之前插入的某个串是当前串的前缀。依据上面两种情况判断结果。
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;

struct Trie
{
    int ch[maxn][10], cnt;
    bool vis[maxn];
    int idx(char ch) { return ch - '0'; }
    bool insert(char* s)
    {
        int u = 0, n = strlen(s);
        bool flag = false;
        for (int i = 0; i < n; i++)
        {
            int c = idx(s[i]);
            if (!ch[u][c])
                ch[u][c] = ++cnt;
            else if (i == n - 1)
                flag = true;
            u = ch[u][c];
            if (vis[u])
                flag = true;
        }
        vis[u] = true;
        return flag;
    }
    void clear()
    {
        cnt = 0;
        memset(ch, 0, sizeof(ch));
        memset(vis, 0, sizeof(vis));
    }
} trie;
char s[20];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        trie.clear();
        bool ans = false;
        for (int i = 1; i <= n; i++)
            scanf("%s", s), ans |= trie.insert(s);
        printf("%s\n", ans ? "NO" : "YES");
    }
    return 0;
}
Last modification:June 25th, 2019 at 11:27 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment