POJ 3630 Phone List：Trie 判斷電話號碼表一致性

題目大意

給定 n (≤ 10000) 個電話號碼（≤ 10 位數字），判斷是否存在某號碼是另一號碼的前綴。存在輸出 NO，否則 YES。

Trie 樹解法

1. 所有號碼插入 Trie，標記結尾 tag++
2. 再次遍歷每個號碼，走到倒數第二字符時，若當前節點 tag > 0，說明有號碼是當前的前綴 → NO
3. 注意：號碼無序，必須全部插入後再判斷

C++ 代碼

struct TrieNode { int tag, next[10]; } trie[100005];
int tot = 0;
char phones[10005][11];

void insert(char* s) {
    int u = 0;
    for (int i = 0; s[i]; ++i) {
        int c = s[i] - '0';
        if (!trie[u].next[c]) trie[u].next[c] = ++tot;
        u = trie[u].next[c];
    }
    trie[u].tag++;
}

bool judge(char* s) {
    int u = 0, len = strlen(s);
    for (int i = 0; i < len - 1; ++i) { // 只檢查到倒數第二位
        int c = s[i] - '0';
        u = trie[u].next[c];
        if (trie[u].tag) return false; // 有號碼在此結尾，是前綴
    }
    return true;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        // 清理 trie
        for (int i = 0; i <= tot; ++i) {
            memset(trie[i].next, 0, sizeof(trie[i].next));
            trie[i].tag = 0;
        }
        tot = 0;
        
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%s", phones[i]);
            insert(phones[i]);
        }
        bool ok = true;
        for (int i = 1; i <= n; ++i) {
            if (!judge(phones[i])) { ok = false; break; }
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

替代方案：排序 + 相鄰比較

將號碼排序，只需檢查相鄰兩個是否有前綴關係。時間 O(n log n × L)，代碼更短。

複雜度

• Trie：O(總長度) ≈ O(n × 10)
• 排序：O(n log n × 10)