leetcode每日一题：49.字母异位词分组

用户7685359

发布于 2020-12-22 15:36:28

3860

发布于 2020-12-22 15:36:28

文章被收录于专栏：FluentStudyFluentStudy

leetcode每日一题：49. 字母异位词分组：https://leetcode-cn.com/problems/group-anagrams/

一起刷题吧

一、题意分析

输入：由字符串组成的列表（数组）输出：将由同样的字母和字母个数组成的不同序列放在一个列表里，然后整体做为一个列表输出

难度：简单标签：哈希、数组

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

注意：

所有输入均为小写字母
不考虑答案输出的顺序

二、参考代码

一种最直观的解决思路就是将字符串排序后的结果做为 key，如果 key 相同则认为是需要放在一组的。在 Python 的 collections 包中有一个 defaultdict ，对于这个场景特别适合。参考代码如下：

from typing import List
from collections import defaultdict


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

        result = defaultdict(list)

        for s in strs:
            result["".join(sorted(s))].append(s)
        return list(result.values())


s = Solution()
print(s.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

这种解法遍历整个数组，同时对字符串做排序，排序的时间复杂度为 O(kLogk)，k 为字符串的长度，因此整个算法的时间复杂度为 O(nkLogk)，n 为列表的长度。那有没有可以优化的地方呢？

其实是有优化的地方的，优化点在于对哈希表 key 的选择，是否可以不用排序来降低时间复杂度呢？这里参考官方题解，通过给字符串中出现的字母计数的思想来做 key，这样 key 的生成时间复杂度可以降为 O(k)，k为字符串长度。这里直接贴上官方的代码，如下：

from typing import List
from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if not strs:
            return []
        mp = defaultdict(list)

        for st in strs:
            counts = [0] * 26
            for ch in st:
                counts[ord(ch) - ord("a")] += 1
            # 需要将 list 转换成 tuple 才能进行哈希
            mp[tuple(counts)].append(st)

        return list(mp.values())

# 作者：LeetCode-Solution
# 链接：https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-12-14，如有侵权请联系 cloudcommunity@tencent.com 删除

nat