当前位置：首页 > article >正文

LeetCode 热题 100 49. 字母异位词分组

article 2025/2/23 4:59:19

LeetCode 热题 100 | 49. 字母异位词分组

大家好，今天我们来解决一道经典的算法题——字母异位词分组。这道题在LeetCode上被标记为中等难度，要求我们将字母异位词组合在一起。下面我将详细讲解解题思路，并附上Python代码实现。

问题描述

给定一个字符串数组 strs，将其中所有字母异位词组合在一起。字母异位词是指由相同字母重新排列形成的单词。

示例：

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

解题思路

核心思想

哈希表分组：
- 使用哈希表（字典）来存储字母异位词的分组结果。
- 将每个字符串排序后的结果作为哈希表的键，原始字符串作为值。
排序作为键：
- 由于字母异位词排序后的结果相同，可以将排序后的字符串作为哈希表的键。
返回结果：
- 遍历哈希表的值，将分组结果存入列表并返回。

Python代码实现

def groupAnagrams(strs):
    from collections import defaultdict

    # 使用 defaultdict 初始化哈希表
    anagrams = defaultdict(list)

    # 遍历字符串数组
    for s in strs:
        # 将字符串排序后作为键
        sorted_s = ''.join(sorted(s))
        # 将原始字符串添加到对应的分组中
        anagrams[sorted_s].append(s)

    # 返回分组结果
    return list(anagrams.values())

# 测试示例
strs1 = ["eat", "tea", "tan", "ate", "nat", "bat"]
strs2 = [""]
strs3 = ["a"]

print(groupAnagrams(strs1))  # 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
print(groupAnagrams(strs2))  # 输出: [[""]]
print(groupAnagrams(strs3))  # 输出: [["a"]]

代码解析

哈希表初始化：
- 使用 defaultdict(list) 创建一个哈希表，键为排序后的字符串，值为原始字符串列表。
遍历字符串数组：
- 对每个字符串进行排序，并将排序后的字符串作为键，原始字符串添加到对应的列表中。
返回结果：
- 将哈希表的值转换为列表并返回。

复杂度分析

时间复杂度：O(n * k log k)，其中 n 是字符串数组的长度，k 是字符串的最大长度。排序每个字符串的时间复杂度为 O(k log k)。
空间复杂度：O(n * k)，用于存储哈希表。

示例运行

示例1

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

示例2

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

示例3

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

优化思路

如果字符串长度较短，可以使用字符计数作为哈希表的键，进一步优化时间复杂度。

优化代码

def groupAnagrams_optimized(strs):
    from collections import defaultdict

    anagrams = defaultdict(list)

    for s in strs:
        # 使用字符计数作为键
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1
        # 将字符计数转换为元组（因为列表不能作为哈希表的键）
        anagrams[tuple(count)].append(s)

    return list(anagrams.values())

# 测试示例
strs1 = ["eat", "tea", "tan", "ate", "nat", "bat"]
strs2 = [""]
strs3 = ["a"]

print(groupAnagrams_optimized(strs1))  # 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
print(groupAnagrams_optimized(strs2))  # 输出: [[""]]
print(groupAnagrams_optimized(strs3))  # 输出: [["a"]]