题目分析

题目要求将一个字符串数组按照字母异位词进行分组。字母异位词指由相同字母以不同顺序构成的单词，例如"eat", "tea", 和 "ate" 是一组字母异位词。输入是一个字符串数组，输出是一个列表，其中每个子列表包含一组字母异位词。

解题思路

为了将字母异位词分组，可以使用一个哈希表（Map），其中键是字符串的标准形式（排序后的字符串），值是一个列表，包含所有属于这个标准形式的字符串。

排序作为键：对每个字符串的字符进行排序，排序后的字符串作为键。
使用哈希表分组：对于每个字符串，将其添加到对应键的列表中。
输出结果：最后，将哈希表的所有值（即分组列表）转换为所需的输出格式。

Java解法

这里提供基于第二种方法（哈希表计数）的 Java 解决方案：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建一个哈希表，用于存储排序后的字符串和对应的原字符串列表
        Map<String, List<String>> map = new HashMap<>();

        // 遍历输入的字符串数组
        for (String str : strs) {
            // 将每个字符串转换为字符数组并进行排序
            char[] array = str.toCharArray();
            Arrays.sort(array);
            // 将排序后的字符数组转换回字符串，作为键使用
            String key = new String(array);
            // 如果这个键不存在于map中，则使用getOrDefault来获取默认的空列表
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            // 将原字符串添加到列表中
            list.add(str);
            // 更新哈希表
            map.put(key, list);
        }
        // 返回哈希表的所有值的列表，这些值本身就是字符串列表
        return new ArrayList<>(map.values());
    }
}

时间复杂度

O(N * K log K)，其中 N 是strs数组的长度，K 是字符串的平均长度。对于每个字符串，我们需要 O(K log K) 时间来进行排序。

空间复杂度

O(N * K)，用于存储哈希表的键和所有原始字符串列表。每个字符串都存储在列表中，并且每个键也是一个字符串。

References

49. 字母异位词分组 ↩︎

趣味算法题