难度: Medium
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
注意：本题相对原题稍作修改
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
Submission
运行时间: 39 ms
内存: 18.6 MB
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = {}
for str in strs:
key = list(str)
key.sort()
key = ''.join(key)
if key in res:
res[key].append(str)
else:
res[key] = [str]
return [value for key, value in res.items()]
Explain
此题解采用了哈希表来对字符串数组进行分类。对于数组中的每一个字符串，我们将其转换为字符列表并进行排序，使得所有的变位词都能得到相同的排序结果作为键（即哈希表的key）。然后，我们将原字符串加入到对应的哈希表条目中。最后，我们从哈希表中收集所有值，每个值都是一个变位词的组合，形成最终的结果列表。
时间复杂度: O(n * m log m)
空间复杂度: O(n * m)
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = {} # 创建一个空字典用于存储变位词组
for str in strs: # 遍历每个字符串
key = list(str) # 将字符串转换为字符列表
key.sort() # 排序字符列表，使得所有变位词都有相同的key
key = ''.join(key) # 将排序后的字符列表重新转换为字符串作为字典的键
if key in res: # 如果这个键已经在字典中，将原字符串添加到对应的列表中
res[key].append(str)
else: # 如果这个键不在字典中，创建一个新的列表
res[key] = [str]
return [value for key, value in res.items()] # 从字典中提取所有列表作为最终的分组
Explore
将字符串转换为字符列表并进行排序可以标准化字符串的形式。无论一个字符串的字符顺序如何，只要它们的字符和每个字符的数量相同，排序后得到的结果都是一样的。因此，排序后相同的字符串必然是变位词，即它们由相同的字符以不同的顺序组成。这种方法通过提供一个统一的标准形式来有效地识别和分组变位词。
是的，在所有情况下，只要输入的是标准字符并且可以被正确排序，这种方法都能保证变位词的正确分组。因为所有的变位词在排序后会得到完全相同的字符串，使用这个排序后的字符串作为哈希表的键确保了所有变位词都映射到同一个键上。这种方法假设字符的排序操作可以反映其等价性，对于标准ASCII字符和基本的Unicode字符，这是适用的。
这取决于Unicode字符或特殊符号的处理方式和排序功能。在大多数现代编程语言中，内置的字符串排序功能能够正确处理Unicode字符，所以一般情况下这个方法是适用的。然而，如果遇到特定的符号或复杂的Unicode字符（如组合字符），可能需要特殊处理才能确保排序的一致性和正确性。此外，对于一些特殊语言环境的排序规则（如带重音符号的字符），默认的排序可能不会按期望的方式工作，这时可能需要自定义排序规则以确保变位词的正确识别和分组。