2026-07-11Leetcode Hot 1002 分钟

27 次阅读

字母异位词分组

本文介绍了 LeetCode 49. 字母异位词分组的两种解法：排序法和计数法，均利用哈希表实现分组。

Leetcode 哈希表 Python

字母异位词分组封面图

题目

https://leetcode.cn/problems/group-anagrams/?envType=study-plan-v2&envId=top-100-liked

解法一

思路

通过哈希表来对字母异位词进行一个收集。通过排序得到字符串的标准排序字符，然后以标准排序字符为key，以所有原本字符串的list为value。最后通过python的list函数将字典转化为二维列表。

代码

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for ch in strs:
            key = "".join(sorted(ch))
            mp[key].append(ch)
        return list(mp.values())

收获

1 创建value为list的字典，用collections.defaultdict(list)
2 字符串排序的方法，"".join(sored(ch))
3 将字典的值转为二维列表的方法，list函数

解法二

思路

和上述使用哈希表的值来作为相同字母异位词的思路相同，只不过将判断字母异位词的方式从排序换成了统计字母出现次数。用26个字母出现次数统计的元组（tuple）来作为哈希表的值

代码

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for str in strs:
            counts = [0] * 26
            for ch in str:
                counts[ord(ch) - ord('a')] += 1
            mp[tuple(counts)].append(str)
        return list(mp.values())

收获

python中数组的初始化方式可以用 * 来表示初始化长度
python中元组可以作为字典的值