1 条题解

  • -1
    @ 2023-3-14 13:23:20
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXNODE = 100000; // 单词数*单词长度(最坏情况下节点数量)
    int tot, root, son[MAXNODE + 5][10];
    int tag[MAXNODE + 5]; // 存在几个单词
    void clearNode(int nId)
    {
        for (int i = 0; i < 10; i++)
            son[nId][i] = 0;
        tag[nId] = 0;
    }
    void ins(const string &s)
    {
        int now = root;
        for (int i = 0; i < s.size(); i++)
        {
            int j = s[i] - '0';
            if (!son[now][j])
            {
                son[now][j] = ++tot;
                clearNode(tot);
            }
            now = son[now][j];
        }
        tag[now]++;
    }
    bool check(const string &s)
    {
        int now = root;
        for (int i = 0; i < s.size(); i++)
        {
            int j = s[i] - '0';
            // 如果前面没有找到,现在要新建节点,那就不存在了
            if (!son[now][j])
                return false;
            now = son[now][j];
            // 如果走到了一个之前存在单词的节点,那就找到了
            if (tag[now])
                return true;
        }
        // 如果最终也没有新建节点,那就说明属于某个单词的前缀
        return true;
    }
    int T, n;
    string s;
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> T;
        while (T--)
        {
            tot = 1;
            root = 1;
            clearNode(tot);
            cin >> n;
            bool flag = false; // 是否存在前缀
            for (int i = 1; i <= n; i++)
            {
                cin >> s;
                flag = flag || check(s);
                if (!flag)
                    ins(s);
            }
            if (flag)
                cout << "NO\n";
            else
                cout << "YES\n";
        }
        return 0;
    }
    
    • 1

    信息

    ID
    691
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    40
    已通过
    20
    上传者