Group Anagram

题目描述

Given an array of strings, group anagrams together.

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

Return:

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

解题方法

判断是否是anagram可以用上一题的思想，但是这里需要快速查找，那么就应该往 hashtable的方向想，本来Counter.items()是list。list是不可以做dictinary的key的，因为它 不是hashable的，所以我们将list转换为tuple。

Solution

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        if not strs:
            return []
        if len(strs) == 1:
            return [strs]

        strs.sort()
        result = {}
        for i in range(len(strs)):
            hashCode = self.hashFunction(strs[i].lower())
            if hashCode in result:
                result[hashCode].append(strs[i])
            else:
                result[hashCode] = [strs[i]]

        return result.values()

    def hashFunction(self, s):
        return tuple(sorted(collections.Counter(s).items()))

Reference