力扣链接：49. 字母异位词分组，难度：中等。
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
约束:
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i]仅包含小写字母
思路
两个字符串，
bat和atb，用什么方法能最快地知道他们是字母异位词呢？点击查看答案
将每个字符串都按字母表顺序排序，然后比较排过序的两个字符串。相等，就是。
但是排序后，原字符串没有被考虑进来，而结果求的是原字符串的分组。如何解决？
点击查看答案
用元组，即把按字母表顺序排序后的字符串和原字符串放在一个元组里，像这样：
("abt", "bat")。剩下要做的，就是对这个元组数组进行分组了。如何分组最简单？
点击查看答案
用
Map，key是按字母表顺序排过序的字符串，value是原字符串的数组。
复杂度
时间复杂度
O(N * M * logM)
空间复杂度
O(N)
解释
M = string.length
Python #
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
pairs = [(''.join(sorted(string)), string) for string in strs]
ordered_to_original = defaultdict(list)
for ordered, original in pairs:
ordered_to_original[ordered].append(original)
return list(ordered_to_original.values())
Ruby #
# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
pairs = strs.map { |string| [ string.chars.sort.join, string ] }
ordered_to_original = Hash.new([])
pairs.each do |ordered, original|
ordered_to_original[ordered] += [original]
end
ordered_to_original.values
end
# Or solution 2: More concise way
# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
strs.group_by { |string| string.chars.sort }.values
end