Group Anagrams

红太狼 2021-12-17 10:39 248阅读 0赞

Given an array of strings, group anagrams together.

For example, given: `["eat", "tea", "tan", "ate", "nat", "bat"]`,  
Return:

[
      ["ate", "eat","tea"],
      ["nat","tan"],
      ["bat"]
    ]

这题其实是算是[Valid Anagram][]的一个follow up。对异位词进行聚类。一开始想到的是对每个单词做set操作，之后作为键值放入字典中。后来想想这种做法实在打错特错，一方面，set本身忽略重复字符，所以‘aate','ate'会被当成一样的词。另外set为可变数据结构，是不能作为hashmap的键值的。

所以此处需要变换思路。如何构建一个忽略字符出现顺序但是考虑出现次数的表示方式。对字符排序是个很好的方式。也即是[Valid Anagram][]的思路，异位词排完序后是完全相同的，之后把它作为键放入hashmap中，单词本身作为value放入hashmap中，最后一个键的值本身就是一个聚类。时间复杂度为O(nklogk)k是字符长度。

空间复杂度为O(nk).代码如下：

class Solution(object):
        def groupAnagrams(self, strs):
            """
            :type strs: List[str]
            :rtype: List[List[str]]
            """
            if not strs:
                return []
            map = {}
            for w in strs:
                val = ''.join(sorted(w))
                if val in map:
                    map[val].append(w)
                else:
                    map[val] = [w]
            return map.values()

另外注意，因为这里全部是小写字母，所以排序时范围非常有限，可以使用count sort 达到一个o(k)的排序复杂度。

转载于:https://www.cnblogs.com/sherylwang/p/5621632.html

[Valid Anagram]: http://www.cnblogs.com/sherylwang/p/5621595.html