如何用哈希表对字母异位词分组？

简化版

字母异位词分组的关键是给同组字符串生成相同 key。常见 key 有排序后的字符串，或 26 个字母计数数组序列化后的字符串。用 Map<key, List<String>> 聚合即可。

详细版

字母异位词是字符种类和次数完全相同、顺序不同的字符串。例如 eat、tea、ate 排序后都是 aet，所以可以作为同一个哈希 key。

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

如果字符串很长且只含小写字母，也可以用 26 位计数生成 key，避免每个字符串排序。

完整版教学

一、分组题的核心是“同类同 key”

哈希表分组类题目，本质是为每个对象提取一个“归一化 key”。只要两个字符串是字母异位词，就必须得到相同 key；不是异位词，就尽量得到不同 key。然后用哈希表把相同 key 的字符串放进同一个列表。

例如 ["eat","tea","tan","ate","nat","bat"]，排序 key 分别是 aet,aet,ant,aet,ant,abt，最终形成三组。

二、排序 key 为什么可行

字母异位词只改变字符顺序，不改变字符多重集合。排序会把同一组字符排列成唯一顺序，所以异位词排序后一定相同。反过来，如果排序后相同，说明字符和次数完全一致，也就是异位词。

eat -> aet
tea -> aet
ate -> aet
tan -> ant
nat -> ant

排序 key 的优点是简单稳妥，适合面试第一版。

三、计数 key 如何优化

如果题目限定只含小写英文字母，可以统计 26 个字母出现次数，再把计数数组序列化成 key。例如 abb 的计数是 a:1,b:2，可以写成 #1#2#0...。

int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
StringBuilder key = new StringBuilder();
for (int x : count) key.append('#').append(x);

计数 key 生成是 O(L)，排序 key 是 O(L log L)。当字符串很长、字符集固定时，计数更合适。

四、为什么 key 不能简单相加或相乘

有人会把字符编码相加作为 key，例如 ab 和 ba 和相同，这是对的；但 ad 和 bc 的字符和也可能相同，这就会把不同组误合并。乘质数也要处理溢出问题，不如排序或计数稳定。

key 方案	正确性	代价
排序字符串	稳定正确	O(L log L)
字母计数	字符集固定时稳定正确	O(L + C)
字符和	会碰撞	不推荐

分组题最怕 key 不唯一导致错误合并。

五、复杂度怎么分析

设有 n 个字符串，平均长度为 L。排序 key 的时间复杂度是 O(n * L log L)，空间复杂度是 O(n * L) 用于结果和 key。计数 key 在固定 26 字母下是 O(n * (L + 26))，通常写作 O(nL)。

哈希表本身负责按 key 聚合，computeIfAbsent 只是减少样板代码，不改变算法本质。

六、常见误区与追问

记忆钩子：异位词分组先别急着分组，先问“什么特征能让同组字符串变成同一个 key”。

误区：用字符编码求和当 key。 不同字符串可能和相同，会错误分组。
误区：计数 key 直接用数组对象。 Java 数组默认按引用比较，必须序列化或包装成可比较对象。
误区：忽略字符集。 若包含 Unicode 或大小写，26 位小写计数不再适用。
追问：排序和计数怎么选？ 排序通用简单，计数在固定小字符集下更快。
追问：分组结果顺序要保证吗？ 普通 HashMap 不保证顺序；若题目要求稳定顺序，可用 LinkedHashMap。
追问：为什么哈希表适合分组？ key 相同的对象能平均 O(1) 定位到同一个桶对应的列表。

七、加强记忆

字母异位词分组的套路是“归一化 key + Map 聚合”。排序 key 把同一组字符排成同一形态；计数 key 把字符多重集合写成固定签名。只要 key 设计正确，分组就变成简单的 Map<key, List>。

简化版

详细版