HOT100-2字母异位词分组

2025-01-14

× 文章目录

1. 1. 解法
2. 2. 代码讲解
3. 3. 代码实现

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

1 2	输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1 2	输入: strs = [""] 输出: [[""]]

示例 3:

1 2	输入: strs = ["a"] 输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

1. 解法

这题的本质是构建一个哈希表，让各字母异位词落在相同的哈希桶中。关键就在于，如何找到一种哈希办法，让各字母异位词能够分别对应起来。

法一：注意到各字母异位词在排序后的顺序相同，因此可以将排序后的字符串作为键

法二：注意到各字母异位词仅是字母的顺序不同，各字母出现的次数必定相同，因此可以定义一个长度为26的列表用于存储各字母出现的次数。再将该列表转化为元组后当作键。（注意：列表由于可修改，因此不能直接作为键，需要改为元组后才行）

法三：在法二的基础上，将列表转化为长度为26的字符串后作为键。

2. 代码讲解

法一：

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

        for str in strs:
            key = "".join(sorted(str))
            if key not in mp:
                mp[key] = [];
            mp[key].append(str)

        return list(mp.values())

在此基础上，可以使用collection库中的defaultdict来新建一个默认值为list的字典，这意味着当我们访问一个不存在的key时，defaultdict 会自动创建一个空列表作为该键的值，也不需要判断key是否在字典中了：

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

        for str in strs:
            key = "".join(sorted(str))
            mp[key].append(str)

        return list(mp.values())

法二：

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

        for str in strs:
            alphabet = [0] * 26
            for letter in str:
                alphabet[ord(letter) - ord("a")] += 1
            mp[tuple(alphabet)].append(str)

        return list(mp.values())

法三：

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

        for word in strs:
            alphabet = [0] * 26
            for letter in word:
                alphabet[ord(letter) - ord("a")] += 1
            hashstr = ''.join(map(str,alphabet))
            mp[hashstr].append(word)

        return list(mp.values())

3. 代码实现

测试用完整代码（以法三为例）：

from typing import List
import collections


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

        for word in strs:
            alphabet = [0] * 26
            for letter in word:
                alphabet[ord(letter) - ord("a")] += 1
            hashstr = ''.join(map(str,alphabet))
            mp[hashstr].append(word)

        return list(mp.values())

# 测试样例
if __name__ == "__main__":
    # 输入
    strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

    # 创建 Solution 对象
    solution = Solution()

    # 调用函数
    result = solution.groupAnagrams(strs)

    # 输出结果
    print("输入:", strs)
    print("分组后的变位词:", result)