LeetCode 49. Group Anagrams 题解

LeetCode 49. Group Anagrams 题解

题目描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1：

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

示例 2：

输入: strs = [""] 输出: [[""]]

示例 3：

输入: strs = ["a"] 输出: [["a"]]

解题思路

哈希表：

• 以排序后的字符串作为键，将字母异位词分组
• 遍历字符串数组，将每个字符串排序后作为键，原字符串作为值

代码实现

def groupAnagrams(strs): from collections import defaultdict anagrams = defaultdict(list) for s in strs: # 排序后的字符串作为键 sorted_str = ''.join(sorted(s)) anagrams[sorted_str].append(s) return list(anagrams.values())

复杂度分析

• 时间复杂度：O(n × k log k)，其中 n 是字符串数量，k 是字符串长度
• 空间复杂度：O(n × k)

优化：字符计数作为键

def groupAnagrams(strs): from collections import defaultdict anagrams = defaultdict(list) for s in strs: # 字符计数作为键 count = [0] * 26 for c in s: count[ord(c) - ord('a')] += 1 anagrams[tuple(count)].append(s) return list(anagrams.values())

测试案例

# 测试案例 1 assert groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) == [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] # 测试案例 2 assert groupAnagrams([""]) == [[""]] # 测试案例 3 assert groupAnagrams(["a"]) == [["a"]]

总结

本题是字符串处理和哈希表的经典应用。

关键点：

• 字母异位词的特征：排序后相同
• 哈希表分组
• 优化：使用字符计数作为键

通过本题可以深入理解哈希表在分组问题中的应用。