极客算法

49. 字母异位词分组(Group Anagrams)

2020-09-14

49. Group Anagrams

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明:

所有输入均为小写字母。

不考虑答案输出的顺序。

排序+哈希

O(N * KlogK), N等于单词个数,K等于单词平均长度

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        seen = {}
        res = []
        
        for word in strs:
            sort_word = ''.join(sorted(word))
            if sort_word in seen:
                index = seen[sort_word]
                res[index].append(word)
            else:
                ans = [word]
                index = len(res)
                res.append(ans)
                seen[sort_word] = index
                
        return res 

哈希

O(N * K), 理论上更快一些,python代码实际并不是

将字符串用数组表示, 例如: “eat”

[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z]
 1           1                                            1 

代码如下:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        seen = {}
        res = []
        base = ord('a')
        
        for word in strs:
            word_count = [0 for i in range(26)] 
            for char in word:
                index = ord(char) - base
                word_count[index] += 1
            # ​换成tuple, 因为list是可变的, 不支持哈希
            word_count = tuple(word_count)
            
            if word_count in seen:
                index = seen[word_count]
                res[index].append(word)
            else:
                ans = [word]
                index = len(res)
                res.append(ans)
                seen[word_count] = index
                
        return res

–End–

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/group-anagrams

Link:https://leetcode.com/problems/group-anagrams/


相关推荐

评论

内容: