难度: Medium
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] 仅包含小写字母运行时间: 68 ms
内存: 19.8 MB
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = defaultdict(list)
for s in strs:
m = [0] * 26
for char in s:
idx = ord(char) - ord('a')
m[idx] += 1
ans[tuple(m)].append(s)
return list(ans.values())
该题解的思路是利用哈希表来将字母异位词分组。具体做法是：遍历字符串数组中的每个字符串，对于每个字符串，统计其中每个字母出现的次数，并将统计结果转换为一个长度为26的元组作为哈希表的键，字符串作为对应键的值。这样，所有字母异位词都会被映射到哈希表中的同一个键上，最后将哈希表中的所有值（即分组后的字母异位词列表）转换为列表返回即可。
时间复杂度: O(n * k)
空间复杂度: O(n)
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = defaultdict(list) # 创建一个默认值为列表的字典，用于存储字母异位词分组
for s in strs: # 遍历字符串数组中的每个字符串
m = [0] * 26 # 创建一个长度为26的列表，用于统计每个字母出现的次数
for char in s: # 遍历当前字符串中的每个字符
idx = ord(char) - ord('a') # 计算字符对应的索引（a-z 对应 0-25）
m[idx] += 1 # 将对应字母的计数加1
ans[tuple(m)].append(s) # 将统计结果转换为元组作为哈希表的键，字符串作为值添加到对应的列表中
return list(ans.values()) # 将哈希表中的所有值（即分组后的字母异位词列表）转换为列表返回
使用长度为26的列表来表示每个字符串的字符出现次数是因为这种方法在空间和时间效率上都很高。由于英文字母只有26个，一个固定大小的数组足以容纳所有可能的字母，并且访问数组元素的时间复杂度是O(1)。相比之下，哈希表虽然灵活但在处理小型固定范围的数据时，其额外的哈希计算和潜在的冲突解决机制可能会导致不必要的开销。数组通过直接使用字母的索引来避免这些问题，因此在处理固定范围数据时更为高效。
将字符出现次数的列表转换为元组用作哈希键的主要原因是元组在Python中是不可变的，因此可以用作哈希表的键。不可变性是必要的，因为哈希表的键必须是不变的以确保哈希表的正确性和稳定性。列表由于是可变的，不能直接用作哈希键。尽管如此，理论上可以使用其他不可变或固定值的数据结构作为哈希键，例如字符串或冻结集合（frozenset），但在这种情况下，由于性能和简便性，元组是最合适的选择。
在哈希表中，两个字符串如果是字母异位词，即使它们的字符顺序不同，它们也会映射到同一个键上，因为它们的字符出现次数是相同的。算法通过统计每个字符串中每个字母的出现次数，并将这些次数存储在一个固定长度的列表（或数组）中，确保了这一点。将这些列表转换为元组后，这些元组将作为哈希键。由于字母异位词具有相同的字符统计数据，因此它们的键（即元组）也将相同，从而确保它们被映射到同一个哈希表条目上。
对于空字符串，该算法同样会创建一个长度为26的数组，其中所有元素的初始值都为0，因为空字符串不包含任何字符。因此，空字符串的字符出现次数列表是全零的列表。将这个列表转换为元组后，得到的元组也将全为零。在哈希表中，所有空字符串都将共享相同的键（即全零的元组），并被分组在一起。这意味着算法能够有效地处理空字符串，将它们归为一组，而不会导致错误或异常。