LeetCode 面试题 10.02. 变位词组

约 4 分钟
文章信息 3 个分类 4 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
数组 字符串 哈希表 排序

题目描述

✅ 面试题 10.02. 变位词组

image-20260929011247467

题意分析

将字符串按变位词关系分组：同组字符串的字母种类和每种字母的出现次数相同，只是排列顺序可以不同。输入只包含小写字母，答案不要求组间或组内顺序，但每个输入字符串都要保留在对应分组中。

解法：排序签名 + 哈希分组

核心思路

[!blue]

逐个把字符串与已有字符串比较，会重复检查许多字符。可以先把每个字符串转换成一个代表整组的规范键，再用哈希表直接定位分组。

将字符排序后，同一种字母的所有副本会排在一起，原来的排列差异被消除。若两个字符串互为变位词，它们的各字母频次相同，排序结果一定相同；反过来，排序结果相同也说明每个字母及其次数完全一致。因此“排序后的字符串相同”恰好等价于“属于同一组”。

哈希表 d 保存“排序签名 → 原字符串列表”。遍历时把当前字符串复制为字符数组 t 并排序，得到键 k，然后把原字符串 s 追加到 d[k]。排序只用于构造键，输出仍保留输入的原始内容。

每个输入只追加一次，所以不会遗漏或额外产生字符串；相同键必属同组，不同键必属不同组，分组也不会混淆。重复出现的相同字符串会按出现次数保留，空字符串则以空键进入同一组。题目不要求输出顺序，最后直接收集哈希表中的所有列表即可。

解题步骤

  1. 创建从签名字符串到分组列表的哈希表。
  2. 对每个输入字符串，复制其字符并排序，将排序结果转换成键。
  3. 获取或创建该键的分组，把原字符串追加进去。
  4. 全部输入处理完后，将哈希表里的分组列表作为结果返回。

代码实现

// 排序后的字符序列是变位词组的规范签名。
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> d = new HashMap<>();

        for (String s : strs) {
            char[] t = s.toCharArray();

            Arrays.sort(t);
            String k = String.valueOf(t);

            d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(d.values());
    }
}

import (
    "sort"
)

// 排序后的字符序列是变位词组的规范签名。
func groupAnagrams(strs []string) (answer [][]string) {
    d := map[string][]string{}
    for _, s := range strs {
        t := []byte(s)
        sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
        k := string(t)
        d[k] = append(d[k], s)
    }
    for _, v := range d {
        answer = append(answer, v)
    }
    return
}

复杂度分析

  • 时间复杂度：设有 $n$ 个字符串，第 $i$ 个长度为 $k_i$。按哈希操作的期望开销计算，总时间为 $O(n+\sum_i k_i\log(k_i+1))$，包括逐串遍历、复制字符、排序和计算键的哈希；即使字符串为空，也需要一次分组操作。
  • 空间复杂度：$O(n+\sum_i k_i)$，用于保存各组的签名和原字符串引用，当前用于排序的字符副本也包含在这个上界内。

关键点总结

[!green]

  • 规范键相等当且仅当互为变位词，使逐个分组可以直接转为哈希查找。
  • 键保存排序后的字符，组内保存原字符串，两者用途不同。
  • 频次必须保留，重复字符串也按输入次数追加，不能用集合代替分组列表。

易错点总结

[!yellow]

  • 只用字符集合做键会丢失字母次数，把不属于同组的字符串混在一起。
  • 把排序签名而不是原字符串加入结果，会改变用户给定的字符串内容。
  • 找到已有分组后应追加元素，不能用当前字符串覆盖整个列表。
  • Java HashMap 和 Go map 不保证固定遍历顺序；本题允许任意输出顺序，不能据此要求答案与示例顺序完全一致。

相似题目

题目 难度 关联与区别
438. 找到字符串中所有字母异位词 中等 都需要识别字母频次相同，本题把完整字符串分组，原题在滑动窗口中寻找匹配。
面试题 01.02. 判定是否互为字符重排 简单 从判断两个串是否同类，扩展为给多个串计算规范键并聚合。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/44881811
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！