华为 OD 训练营 · 题解精讲

LC49. 字母异位词分组

题目描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。示例 1: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 示例 2: 输入: strs = [""] 输出: [[""]] 示例 3: 输入: strs = ["a"] 输出: [["a"]] 提示： 1 <= strs.length <= 10^4 0 <= strs[i].length <= 100 strs[i] 仅包含小写字母

题目解析

解题思路

本题的核心在于为每个字符串生成一个唯一的“签名”，使得互为字母异位词的字符串拥有相同的签名，而非异位词的签名不同。参考代码采用计数法：由于字符串仅包含小写字母，可以用一个长度为 26 的数组记录每个字母出现的次数，然后将该数组转换为一个固定格式的字符串作为哈希表的键。

用到的数据结构是哈希表（字典），键为签名，值为属于该签名的字符串列表。遍历所有字符串，对每个字符串生成签名，将其加入哈希表对应键的列表中，最后返回哈希表的所有值即可。

关键步骤

1. 初始化哈希表：使用 collections.defaultdict(list)，避免手动检查键是否存在。 2. 统计字母频次：对每个字符串 s，创建长度为 26 的列表 counts，遍历 s 中每个字符 c，执行 counts[ord(c) - ord('a')] += 1。 3. 生成签名：将 counts 中的每个数字前加上 # 拼接成一个字符串，例如 "#1#0#0...#0"。这样保证了不同频次分布对应不同的键。


   示例：字符串 "abc" → counts = [1,1,1,0,...] → key = "#1#1#1#0#0#0..."

4. 分组：mp[key].append(s) 将当前字符串加入对应分组。 5. 返回结果：list(mp.values()) 将字典的所有值（列表的列表）转换为输出格式。

复杂度分析

时间复杂度：O(N * K)，其中 N 是字符串数组长度，K 是字符串的最大长度。每个字符串需要遍历一次统计频次（O(K)），生成签名和哈希操作均为 O(1)。
空间复杂度：O(N * K)，哈希表存储所有字符串，每个字符串的签名长度固定为 26*2（每个数字前加 #），但签名本身不随字符串长度变化，因此主要空间开销是存储所有字符串本身。

参考代码

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 互为字母异位词的两个字符串包含的字母相同
        # 因此两个字符串中的相同字母出现的次数一定是相同的
        # 可以将每个字母出现的次数使用字符串表示，作为哈希表的键
        mp = collections.defaultdict(list)

        for s in strs:
            # counts 代表每个小写字母出现的频次
            counts = [0] * 26

            # 利用 for 循环，统计 str 当中每个字母出现的频次
            for c in s:
                counts[ord(c) - ord('a')] += 1

            # 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            key = ''.join(['#'+str(count) for count in counts])

            # 在哈希表 mp 当中找出这个 key 对应的字符串 str 来
            # 1、如果有这个 key，那么这个 key 对应的 数组 会新增一个 str 进去
            # 2、如果没有这个 key，那么会初始化一个数组，用来新增这个 str
            mp[key].append(s)

        # 返回结果
        return list(mp.values())

← 上一篇

LC45. 跳跃游戏II

LC55. 跳跃游戏