Jianbo Dai's

mq036.字母异位词分组

 
  • Dec 08, 2020

题目链接

一开始我还以为要考虑两个完全一样的词要不要排除呢看来不需要那么更简单了，介绍两种思路，一种是将单词里的字母排序，另外一种是用26个数字编码单词。前一个个算法的时间复杂度是O（NKlogK），K是字符串的最大长度。空间复杂度是O（NK）。后一个算法的时间和空间复杂度都是O（NK）。

class Solution:
    def groupAnagrams1(self, strs: List[str]) -> List[List[str]]:
        res = collections.defaultdict(list)
        for s in strs:
            ranked = "".join(sorted(s))
            res[ranked].append(s)
        return list(res.values())

    def groupAnagrams2(self, strs):
        res = collections.defaultdict(list)
        for s in strs:
            embedding = [0]*26
            for c in s:
                embedding[ord(c)-ord("a")] += 1
            res[tuple(embedding)].append(s)
        return list(res.values())
Search