POJ 3630 Phone List：Trie 树判断前缀冲突

题目大意

给定 n 个电话号码字符串，判断是否存在某号码是另一号码的前缀。存在输出 "NO"，否则 "YES"。

Trie 树插入检测

1. 插入每个字符串
2. 插入过程中两种冲突：
   • 路径上遇到已标记为单词结尾的节点 → 当前串是已有串的前缀
   • 插入完毕后，当前节点仍有子节点 → 已有串是当前串的前缀
3. 任一冲突即答案为 NO

结构体实现 Trie

struct Node {
    int id, val;
    Node* ch[10]; // 数字 0-9
} nod[MAXN], *root, *null;

void init() {
    null = &nil; nil.id = 0;
    newNode(root);
}

void newNode(Node* &x) {
    x = &nod[sz++];
    x->val = 0; x->id = sz;
    for (int i = 0; i < 10; ++i) x->ch[i] = null;
}

void insert(char* str) {
    int len = strlen(str);
    Node* p = root;
    for (int i = 0; i < len; ++i) {
        int k = str[i] - '0';
        if (p->ch[k] == null) newNode(p->ch[k]);
        if (p->val) flag = 1; // 已有串是当前串前缀
        p = p->ch[k];
    }
    p->val = 1;
    for (int i = 0; i < 10; ++i)
        if (p->ch[i] != null) { flag = 1; break; } // 当前串是已有串前缀
}

完整主程序

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        init(); flag = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%s", str);
            insert(str);
        }
        puts(flag ? "NO" : "YES");
    }
    return 0;
}

复杂度

• 时间：O(总字符数)
• 空间：O(总字符数 × 字符集大小)

替代方案：排序 + 相邻比较

sort(strs, strs+n);
for (int i = 1; i < n; ++i)
    if (strs[i].starts_with(strs[i-1])) return "NO";
return "YES";

时间 O(n log n × 平均长度)，实现更简短，适合字符串长度不大时使用。