Phone List

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1379 字
数字串建 Trie，插入时双向判前后缀
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1471
// 题意：T 组数据，每组 n 个数字串，判断其中是否存在一个串是另一个串的前缀；存在输出 NO，不存在输出 YES。
// 思路：逐个插入 Trie。插入途中若经过某个已标记为单词结尾的结点，说明已有短串是当前串的前缀；插完后再看该结点是否已有子结点，若有说明当前串是已有长串的前缀。两种情况任一成立即判定为 NO。
// 复杂度：O(所有串总长度) 时间 / O(所有串总长度 × 字符集) 空间
// 易错点：输出是反的，存在前缀关系才输出 NO，别按直觉写反。
// 易错点：多组数据必须重建 Trie，否则上一组的单词结尾标记会污染下一组判定。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[10];
    bool ed;
    Node(){
        memset(ch, 0, sizeof(ch));
        ed = false;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if(!(cin >> T)) return 0;
    while(T--){
        int n;
        cin >> n;
        vector<Node> tr;
        tr.reserve(n * 10 + 1);
        tr.push_back(Node());
        bool bad = false;
        for(int i = 0; i < n; i++){
            string s;
            cin >> s;
            int u = 0;
            for(int j = 0; j < (int)s.size(); j++){
                int c = s[j] - '0';
                if(!tr[u].ch[c]){
                    tr[u].ch[c] = (int)tr.size();
                    tr.push_back(Node());
                }
                u = tr[u].ch[c];
                if(tr[u].ed) bad = true;
            }
            tr[u].ed = true;
            for(int c = 0; c < 10; c++){
                if(tr[u].ch[c]) bad = true;
            }
        }
        cout << (bad ? "NO" : "YES") << "\n";
    }
    return 0;
}
Phone List

正文

一本通·提高篇的其它内容
