有勇气的牛排博客
☰

LeetCode 049 字母异位分组

有勇气的牛排 27 算法 2025-08-04 22:00:46
进群口令：博客

题目

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

示例1：

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

解释：

  • 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
  • 字符串 “nat” 和 “tan” 是字母异位词，因为他们可以重新排列形成彼此。
  • 字符串 “ate”，“eat”，“tea” 是字母异位词，因为他们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = [“a”]

输出: [[“a”]]

提示：

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

排序法(常用，易实现)

核心：字母异位词排序后想同。例如：

"eat" → "aet"
"tea" → "aet"

这样可以用排序后的字符串作为分组的key。

复杂度：

  • 时间：O(N × K logK)
  • 空间：O(N × K)

优点：

  • 思路直观，代码简单
  • 排序后作为key非常容易

缺点：

  • 排序多了个 logK 因子
  • 如果字符串很长，排序会耗时
# -*- coding: utf-8 -*-
from collections import defaultdict


def groupAnagrams(strs):
    groups = defaultdict(list)
    for str in strs:
        str_sort = "".join(sorted(str))
        groups[str_sort].append(str)

    return list(groups.values())


strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(groupAnagrams(strs))

strs = ["a"]
print(groupAnagrams(strs))

strs = [""]
print(groupAnagrams(strs))

image.png

计数法（高效）

核心：26个小写字母，用一个长度为26的元组作为唯一标识

步骤：

  1. 对每个字符串，用数组计数26个字母出现次数。
  2. 把该计数数组转成元组作为key。
  3. 存储哈希表分组。

复杂度：

  • 时间O(N × K)（比排序法少了个 logK 因子）
  • 空间：O(N × 26)

优点：

  • 更快，尤其是 K 大时
  • 不依赖排序

缺点：

  • 代码比排序法稍长
# -*- coding: utf-8 -*-
from collections import defaultdict


def groupAnagrams(strs):
    groups = defaultdict(list)
    for str in strs:	# O(n)
        count = [0] * 26
        for char in str:	# O(k)
            count[ord(char) - ord('a')] += 1
        groups[tuple(count)].append(str)

    return list(groups.values())


strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(groupAnagrams(strs))

strs = ["a"]
print(groupAnagrams(strs))

strs = [""]
print(groupAnagrams(strs))

错误思路

假设取每个字母的 ASCII 码作为key。

这种方案不能正确区分所有字母异位词，会出现哈希冲突：

反例：

"ad" → ord('a') + ord('d') = 97 + 100 = 197
"bc" → ord('b') + ord('c') = 98 + 99  = 197

"ad" 和 "bc" 不是字母异位词，但它们的 ASCII 码和一样，会被错误分到同一组。

所以这个算法 不是一个可靠的分组依据。

评论区

×
×