Given an array of strings, group anagrams together.

Example:

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
  Input: ["eat", "tea", "tan", "ate", "nat", "bat"] 
Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter

思路

　　这道题在一开始看到的时候，没有什么具体的思路。但是在想了一会之后觉得可以使用辅助字段来解决该问题。意思就是我们对列表中的字符串进行排序，然后将相同的添加进同一列表中。当遍历完毕之后得到最后的结果。时间复杂度为O(n mlog m),其中n为列表的长度，m为其中最长的字符串长度。空间复杂度为O(n*m)。

　　在后面看到别人的解答之后学习到了另一种思路就是因为字符只有26个，所有我们设置一个列表，其中包含26个0，然后对列表中每一个字符串进行统计相应的字母出现的次数，然后把他加到相应的位置，然后将其转化为元祖并利用字典，将其对应的字符串添加到对应的列表中。时间复杂度复杂度为O(n*m), n为列表的长度，m为最长的单词数。空间复杂度为O(n*m)。

第一种思路的解决代码

 

1 class Solution(object): 2     def groupAnagrams(self, strs): 3         ans = collections.defaultdict(list) # 辅助字典 4         for s in strs: 5  ans[tuple(sorted(s))].append(s) # 排序之后将其添加到对应的列表中 6         return ans.values()   # 返回列表

第二种思路的解决代码

 

1 class Solution(object): 2     def groupAnagrams(self, strs): 3         hmap = collections.defaultdict(list) 4         for st in strs: 5             array = [0] * 26         # 26个元素的列表
6             for l in st: # 将字符串元素计数 7                 array[ord(l) - ord('a')] += 1  
8  hmap[tuple(array)].append(st) # 按照元素出现的个数进行添加 9         return hmap.values()
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄