Sort Me：字典樹實現自定義字母序排序

Sort Me 題解：基於字典樹的自定義字母序排序

題目背景： Gorellians 每年重新定義英文字母順序，給定一個排列 s（26 大寫字母的排列）和 n 個單詞，按 s 定義的字典序輸出單詞。n ≤ 20，單詞長度 ≤ 30。

核心思路

• 構建映射 Order[c] = c 在 s 中的位置，將自定義字母序轉換為整數順序。
• 將所有單詞插入字典樹：按照 Order 映射後的字符順序建立子節點。
• 字典樹節點包含 flag（單詞結束計數）和 next[26] 指針。
• 先序遍歷字典樹（按 0~25 順序遍歷子節點），輸出所有單詞即為排序結果。

算法步驟

1. 讀入 n，若 n=0 結束。
2. 讀入字母排列 s，建立 Order[26]。
3. 初始化字典樹根節點。
4. 讀入 n 個單詞，調用 insert 插入字典樹。
5. 輸出 "year k"，調用 print 遞歸遍歷輸出。

關鍵代碼

#include <cstdio>
#include <cstring>
typedef struct nn {
    int flag;
    struct nn *next[26];
} node;
node *root;
node *builde() {
    node *p = new node;
    for (int i = 0; i < 26; i++) p->next[i] = NULL;
    p->flag = 0; return p;
}
char str[50], s[50];
int Order[50];
void insert() {
    node *p = root;
    for (int i = 0; str[i]; i++) {
        int j = Order[str[i] - 'A'];
        if (!p->next[j]) p->next[j] = builde();
        p = p->next[j];
    }
    p->flag++;
}
void print(node *p, int len) {
    if (p->flag) {
        for (int i = 1; i <= p->flag; i++) printf("%s\n", str);
    }
    for (int i = 0; i < 26; i++)
        if (p->next[i]) {
            str[len] = s[i];
            str[len+1] = '\0';
            print(p->next[i], len+1);
        }
}
int main() {
    int t = 0, n;
    while (scanf("%d", &n) && n) {
        scanf("%s", s);
        for (int i = 0; i < 26; i++) Order[s[i] - 'A'] = i;
        root = builde();
        while (n--) { scanf("%s", str); insert(); }
        printf("year %d\n", ++t);
        print(root, 0);
    }
    return 0;
}

複雜度分析

插入單詞總長度 L ≤ 600，構建字典樹 O(L)。遍歷輸出 O(L)。空間 O(L)。極高效。

替代方案

也可直接用 std::sort 配合自定義比較器，但字典樹方法更能體現「字典序」本質，且易於擴展（如前綴查詢）。