字母异位词分组
来源：力扣（LeetCode）
著作权归领扣网络所有。
题目描述：给定一个符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
解答类似的字母异位等问题，可以考虑引入字典，将KEY值储存为字符串。
方法一：排序数组分类
思路
当且仅当他们的排序字符串相等时，两个字符串是字母异位词。
算法
维护一个映射 ans:{String->List}，其中每个键K是一个排序字符串，每个值是初始输入的字符串列表，排序后等于K。
python
class Solution(object):
def gropAnagrams(self,strs):
ans = collection.defaultdict(list)
for s in strs:
ans[tuple(sorted(s))].append(s)
return ans.values()
复杂度分析
- 时间复杂度：O（N K logK），其中K是
strs是长度，而K是strs中字符串的最大长度，当我们遍历每个字符串是，外部循环具有的复杂度为O(N)。然后，我们在O(K logK)的时间内对每个字符串排序。 - 空间复杂度：O(N K)，排序存储在
ans中的全部信息内容。
方法二：按计数分类
思路
当且仅当他们的字符计数（每个字符的出现次数）相同时，两个字符串是字母异位词。
算法
我们可以将每个字符串s转换为字符数count，由26个非负整数组成，表示a，b，c的数量等。我们使用这些计数作为哈希映射的基础。
python
class Solution:
def groupAnagrams(strs):
ans = collections.defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
ans[tuple(count)].append(s)
return ans.values()
复杂度分析
时间复杂度：O(NK)O(NK)，其中 NN 是 strs 的长度，而 KK 是 strs 中字符串的最大长度。计算每个字符串的字符串大小是线性的，我们统计每个字符串。
空间复杂度：O(NK)O(NK)，排序存储在 ans 中的全部信息内容。
