POJ 3630 Phone List：字典序排序 + 前綴判斷

題目大意

給定 n（≤10000）組電話號碼（長度 ≤10），判斷是否存在一個號碼是另一個號碼的前綴。若存在輸出 NO，否則 YES。

解題思路

1. 將所有號碼以字串形式讀入。
2. 以字典序排序（qsort + strcmp）。
3. 排序後，若某號碼是下一個號碼的前綴，兩者必相鄰。只需檢查相鄰兩字串是否有前綴關係。

代碼實現

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Node { char s[20]; } b[10010];

int cmp(const void *a, const void *b) {
    return strcmp((*(struct Node*)a).s, (*(struct Node*)b).s);
}

bool hasPrefix(int n) {
    for (int i = 0; i < n - 1; ++i) {
        int len = strlen(b[i].s);
        int j = 0;
        for (; j < len; ++j)
            if (b[i].s[j] != b[i+1].s[j]) break;
        if (j == len) return true; // b[i] 是 b[i+1] 的前綴
    }
    return false;
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%s", b[i].s);
        qsort(b, n, sizeof(b[0]), cmp);
        puts(hasPrefix(n) ? "NO" : "YES");
    }
    return 0;
}

複雜度分析

• 排序：O(n log n × L)，L 為字串長度（≤10）。
• 掃描：O(n × L)。
• 空間：O(n × L)。

替代方案：Trie 樹

亦可用 Trie 樹插入時檢查是否已有節點標記為終結，或插入後發現當前節點已有子節點，同樣可在 O(n × L) 解決，但排序法程式碼更短、常數更小。