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 ，对于这个场景特别适合。参考代码如下：
代码语言：javascript复制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为字符串长度。这里直接贴上官方的代码，如下：
代码语言：javascript复制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）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
