leetcode_字符串 49. 字母异位词分组

49. 字母异位词分组

• 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
• 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
• 示例 1:

• 输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
• 输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

• 示例 2:

• 输入: strs = [“”]
• 输出: [[“”]]

• 示例 3:

• 输入: strs = [“a”]
• 输出: [[“a”]]

• 思路：

• 1. 字母异位词的特点是它们包含的字母种类和数量完全相同，只是排列顺序不同。因此，可以利用排序法来识别哪些单词是字母异位词（26字母表顺序）。
• 2. 创建一个哈希表，键是排序后的字符串，值是对应的字母异位词列表。遍历字符串数组，将每个单词排序后作为键，并将单词添加到对应的字母异位词列表中。

class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
# 使用哈希表来存储分组结果
hash_map = {}
# 遍历每个单词
for word in strs:
# 对单词进行标准化（排序字母）
sorted_word = ''.join(sorted(word))
if sorted_word not in hash_map:
hash_map[sorted_word] = []
# 为键sorted_word创建一个新的键值对，值是一个空列表
# 例如：hash_map = {"aet": []}
# 将当前单词添加到对应的分组中
hash_map[sorted_word].append(word) # 因为键所对应的值是一个列表，所以用append
# 返回哈希表中的所有分组
return list(hash_map.values())

• 时间复杂度: O(n * k * logk), n是单词数量, k是单词的最大长度
• 空间复杂度：O(n*k), n是单词的数量, k是单词的平均长度