题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

我的解法——字符串排序+hash（AC）

python中，每个str排序后转为tuple，这样可以直接存储到dict
时间复杂度O(nlogn)，空间复杂度O(n)
Beat 12%

class Solution:
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        dic = {}
        
        for word in strs:
            now = str(sorted(word))
            if(now in dic):
                dic[now].append(word)
            else:
                dic[now] = [word]
                
        res = []
        for word in dic:
            res.append(dic[word])
        
        return res

其他解法——字符出现次数+hash

当且仅当它们的字符数（每个字符的出现次数）相同时，两个字符串才是一样的。将各个字符的出现次数存到tuple中（tuple长度为26），然后作为dict的key
时间复杂度O(n)，空间复杂度O(n)

参考答案

https://leetcode.com/problems/group-anagrams/solution/