字母异位词分组：排序键与哈希表

核心结论#

两个字符串互为字母异位词，当且仅当它们排序后的字符序列相同。遍历输入时，把排序结果作为哈希表的键，把原字符串追加到对应分组即可。

问题与约束#

给定字符串数组，例如 ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']，需要把字母组成相同、排列不同的字符串放进同一组。分组和组内元素的返回顺序不影响正确性。

核心机制#

对每个字符串执行三步：

1. 转成字符数组并排序。
2. 用排序结果构造稳定的分组键。
3. 将原字符串加入该键对应的列表。

eat、tea 和 ate 都会生成键 aet，因此自然进入同一组。不同字符多重集合不可能得到同一个排序键。

Java 实现#

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            groups.computeIfAbsent(key, ignored -> new ArrayList<>()).add(str);
        }

        return new ArrayList<>(groups.values());
    }
}

正确性与复杂度#

排序键完整保留字符及其出现次数，所以同组字符串一定互为字母异位词，互为字母异位词的字符串也一定得到同一个键。

设字符串数量为 n，最长字符串长度为 k：

• 时间复杂度：O(n * k log k)。
• 额外空间复杂度：O(n * k)，用于分组键和结果。

验证#

至少覆盖以下输入：空数组、单个空字符串、重复字符串，以及包含多个分组的常规样例。比较结果时应忽略组间顺序。

参考#

• LeetCode 49：字母异位词分组