变位词：签名与排序

C · 变位词：签名与排序

来源：《编程珠玑》开篇问题 C

题意

给定一本英文词典，找出所有变位词集合。
例：pots、stop、tops 互为变位词（字母相同、顺序不同）。

朴素：两两比较 → 对词典规模平方级，太慢。

思路：签名 + 排序

1. 对每个单词算一个签名：把字母排序后的串
   • pots → opst
   • stop → opst
   • tops → opst
2. 按签名把单词排序 / 分组（或放进 Map<签名, List<单词>>）
3. 同一签名下、且单词不止一个 → 一组变位词

本质：把「乱序相等」变成「签名相等」，再交给排序或哈希。

原理图

新标签打开流程图

交互演示

新标签打开演示

Java 伪代码

Map<String, List<String>> groupAnagrams(List<String> dict) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String word : dict) {
        String sig = signature(word); // 字母排序
        groups.computeIfAbsent(sig, k -> new ArrayList<>()).add(word);
    }
    // 只保留 size >= 2 的组，即真正的变位词集合
    groups.entrySet().removeIf(e -> e.getValue().size() < 2);
    return groups;
}
 
String signature(String word) {
    char[] cs = word.toLowerCase().toCharArray();
    Arrays.sort(cs);
    return new String(cs);
}

若坚持「珠玑味」的外部排序思路：先输出 (签名, 原词)，按签名排序，再顺序扫一遍聚成组。

复杂度

签名	每词 (O(L \log L))（(L) 为词长）
分组	哈希约 (O(N))；或排序 (O(N \log N))

系列

• 编程珠玑索引