LeetCode 49 [Group Anagrams]

原题

给出一个字符串数组S，找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串，那么他存在一个字母集合相同，但顺序不同的字符串也在S中。

对于字符串数组 ["eat", "tea", "tan", "ate", "nat", "bat"]
返回

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

解题思路

• 首先，注意返回结果中，子字符串数组内要保持有序，所以第一步先把strs排序
• 本题考察使用hashtable，与直接判断两个字符串是否是anagram不同，遍历一遍字符串数组，将排序的字符串作为key，把原始字符串作为value
• 最后遍历hashtable生成结果

完整代码

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        strs.sort()
        d = {}
        for str in strs:
            if "".join(sorted(str)) not in d:
                d["".join(sorted(str))] = [str]
            else:
                d["".join(sorted(str))].append(str)
                
        res = []
        for key, value in d.items():
            res.append(value)
        return res