《算法競賽入門經典》例題 5.32：字母重排——排序標準化與查找匹配

《算法競賽入門經典》例題 5.32：字母重排——排序標準化與查找匹配

本題核心思想：**字母順序無關時，將字符串排序作為「指紋」比較**。通過預處理字典構建有序索引，實現高效異構詞查找。

一、題目重述

• 輸入：字典單詞列表 (以 ****** 結束)，隨後多個查詢單詞
• 任務：對每個查詢詞，輸出字典中所有字母重排後相同的單詞，按字典序
• 約束：單詞長度 ≤ 6，小寫字母，字典不保證有序

二、算法設計

核心洞察

兩單詞字母重排等價 ⇔ 排序後字符串相同

"listen" → 排序 → "eilnst"
"silent" → 排序 → "eilnst"
→ 判定為字母重排關係

預處理策略

1. 讀入字典所有單詞
2. 對字典單詞**按字典序排序** (保證輸出順序)
3. 為每個單詞計算「指紋」：字符排序後的字符串
4. 存儲 word[i] (原詞) 和 sorted[i] (指紋)

查詢處理

1. 讀入查詢詞 s
2. 計算 s 的指紋：qsort(s, len, sizeof(char), cmp_char)
3. 遍歷字典，比較 sorted[i] == s_fingerprint
4. 匹配則輸出 word[i] (原詞，非排序後)
5. 無匹配輸出 :()

三、完整代碼實現 (標準 C，兼容 UVa/OJ)

#include 
#include 
#include 

#define MAX_WORDS 2000
#define MAX_LEN 10

char word[MAX_WORDS][MAX_LEN];
char sorted[MAX_WORDS][MAX_LEN];
int n = 0;

// 字符比較：用於 qsort 排序單字符
int cmp_char(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}

// 字符串比較：用於 qsort 排序字典
int cmp_str(const void* a, const void* b) {
    return strcmp((char*)a, (char*)b);
}

int main() {
    // 1. 讀入字典
    while (scanf("%s", word[n]) == 1) {
        if (word[n][0] == '*') break;  // 結束標記
        n++;
    }
    
    // 2. 字典按字典序排序 (保證輸出順序)
    qsort(word, n, sizeof(word[0]), cmp_str);
    
    // 3. 計算每個單詞的指紋
    for (int i = 0; i < n; i++) {
        strcpy(sorted[i], word[i]);
        qsort(sorted[i], strlen(sorted[i]), sizeof(char), cmp_char);
    }
    
    // 4. 處理查詢
    char query[MAX_LEN];
    while (scanf("%s", query) == 1) {
        // 計算查詢詞指紋
        qsort(query, strlen(query), sizeof(char), cmp_char);
        
        int found = 0;
        for (int i = 0; i < n; i++) {
            if (strcmp(sorted[i], query) == 0) {
                if (!found) found = 1;
                printf("%s ", word[i]);  // 輸出原詞
            }
        }
        if (!found) printf(":(");
        printf("\n");
    }
    return 0;
}

四、關鍵技術點解析

五、複雜度分析

• 預處理：O(n log n × L + n × L log L) (字典排序 + 指紋計算)，L ≤ 6
• 單次查詢：O(L log L + n × L) (查詢排序 + 線性掃描)
• 空間：O(n × L)
• 給定 L ≤ 6, n ≤ 2000，極其高效

六、優化方向：Hash 表索引

若字典極大 (如 10 萬詞)，線性掃描過慢，可構建：

// 映射：指紋 → 原詞列表 (鏈表/動態數組)
HashMap>

// 查詢：計算指紋 → O(1) 定位列表 → 直接輸出
// 需實現哈希表或使用 uthash / C++ unordered_map

七、測試用例

輸入：
listen
silent
enlist
google
goo
*
listen
silent
abc

輸出：
listen silent enlist
listen silent enlist
:(

八、避坑指南

1. 結束標記：****** (六個星號)，非單個 *
2. 輸入結束：查詢詞讀到 EOF (文件結尾/管道關閉)
3. 大小寫：題目明確小寫，若未說明需統一 tolower
4. 重複單詞：字典可能含重複詞，輸出時保留重複 (或按需去重)
5. 格式符：%s 讀取以空白分隔的詞，自動處理換行

九、舉一反三：相關經典題

• UVa 156 - Ananagrams：找無異構詞的單詞
• LeetCode 49 - Group Anagrams：分組異構詞
• LeetCode 438 - Find All Anagrams in a String：滑動窗口 + 字符計數
• 異構詞判定：排序法 O(L log L) vs 計數法 O(L + Σ)

總結

「排序標準化」是處理順序無關等價關係的通用技巧：**將無序結構映射為有序標準形式**，轉化為精確匹配問題。本題展示了預處理 + 指紋匹配的經典模式，適用於異構詞、同構圖、多集合相等等場景。掌握 qsort 靈活運用、比較函數編寫、預計算權衡，是算法競賽基本功。