HDU 1671 Phone List：字典樹 (Trie) 判斷前綴一致性

HDU 1671 Phone List：字典樹 (Trie) 判斷前綴一致性

給定一組電話號碼，判斷是否存在某號碼為另一號碼前綴的情況。若存在則輸出 "NO"，否則 "YES"。經典字典樹 (Trie) 應用。

問題分析

若號碼 A 是號碼 B 的前綴，則在 Trie 中插入 A 後，插入 B 時會經過 A 的終結節點；反之亦然。因此，插入所有號碼後，再查詢每個號碼：若查詢過程中遇到終結標記且尚未走完該號碼，或走完該號碼後該節點仍有子節點，則存在前綴關係。

Trie 結構設計

• 節點包含 next[10] 指針陣列 (對應數字 0-9) 與 tail 標記是否為號碼結尾。
• 插入 in_Trie：逐字符遍歷，節點不存在則創建，最後標記 tail=1。
• 查詢 query：遍歷字符，若中途遇到 tail=1 且非最後字符，返回 true (發現前綴)；若走完字符但該節點有子節點，亦返回 true。
• 釋放 dele：遞歸刪除子節點，防止記憶體洩漏。

完整代碼 (C++)

#define LOCAL
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

struct Trie {
    Trie *next[10];
    bool tail;
};

char str[10005][12];

void in_Trie(char *s, Trie *root) {
    Trie *cur = root, *newcur;
    for (int i = 0; s[i] != '\0'; i++) {
        if (cur->next[s[i]-'0'] == NULL) {
            newcur = new Trie;
            for (int j = 0; j <= 9; j++) newcur->next[j] = NULL;
            newcur->tail = 0;
            cur->next[s[i]-'0'] = newcur;
        }
        cur = cur->next[s[i]-'0'];
    }
    cur->tail = 1;
}

bool query(char *s, Trie *root) {
    int i = 0;
    Trie *cur = root;
    for (i = 0; s[i]; i++) {
        if (cur->tail == 0 && cur->next[s[i]-'0'] != NULL)
            cur = cur->next[s[i]-'0'];
        else break;
    }
    if (s[i] != '\0') return 1;
    return 0;
}

void dele(Trie *root) {
    for (int i = 0; i <= 9; i++)
        if (root->next[i] != NULL) dele(root->next[i]);
    delete root;
}

int main() {
    #ifdef LOCAL
    freopen("test.in", "r", stdin);
    #endif
    int t, i, n;
    Trie *root;
    scanf("%d", &t);
    while (t--) {
        root = new Trie;
        for (int j = 0; j <= 9; j++) root->next[j] = NULL;
        root->tail = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            scanf("%s", str[i]);
            in_Trie(str[i], root);
        }
        for (i = 0; i < n; i++)
            if (query(str[i], root) != 0) break;
        dele(root);
        if (i >= n) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

複雜度與優化

時間 O(總字符長度)，空間 O(總字符長度)。亦可先按長度排序，僅檢查較短號碼是否為較長號碼前綴，簡化邏輯。