leetcode-hot-49

LeetCode 49. 字母异位词分组（Group Anagrams）总结

📋 问题描述

给定一个字符串数组 strs，将其中所有字母异位词组合在一起。字母异位词是由重新排列源单词的所有字母得到的新单词。

示例：

text

输入: strs = ["eat","tea","tan","ate","nat","bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

💡 解决方案

方法思路

使用哈希表来分组异位词：

• 键（Key）：将每个字符串排序后得到的标准化字符串（异位词排序后相同）
• 值（Value）：存储原始字符串的列表
• 遍历每个字符串，排序后作为键，将原始字符串添加到对应的列表中
• 最后返回哈希表中所有值的集合

代码实现

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);
            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 是字符串数组的长度，k 是字符串的平均长度
  • 每个字符串需要排序（O(k log k)）
  • 需要处理 n 个字符串
• 空间复杂度：O(n × k)
  • 哈希表需要存储所有字符串

🔑 关键点

1. 异位词特性：异位词排序后相同，因此排序后的字符串可作为哈希表的键
2. 哈希表使用：使用 getOrDefault 方法简化代码，避免不必要的判断
3. 结果返回：直接使用 new ArrayList<>(map.values()) 将哈希表的值转换为列表