字母异位词分组

来源：力扣（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 中的全部信息内容。