LeetCode 面试题 10.02. 变位词组

2026-03-28 HGNULB 约 4 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 面试题 10.02. 变位词组

题意分析

把字符串数组按“互为变位词”分组。两个字符串互为变位词，当且仅当它们包含相同字符及相同频次，字符原本的排列顺序无关。

分组问题的关键不是两两比较，而是为每个字符串构造一个规范签名：同组字符串的签名必须相同，不同组签名必须不同。有了签名，只需一次遍历，用哈希表把原字符串追加到对应桶中。

空字符串的签名也是空字符串，多个空串会自然进入同一组；题目不要求组间顺序，因此直接遍历哈希表的 values 即可。若要求稳定输出，则还要额外维护首次出现顺序，不能依赖哈希表迭代顺序。

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

核心思路

把一个字符串的字符排序后，所有排列差异都会被消除："eat"、"tea"、"ate" 都变成 "aet"。反过来，如果两个排序结果相同，它们每种字符的频次必然相同，所以确实互为变位词。排序串因此是无碰撞的规范签名。

哈希表 groups 维护“签名 → 原字符串列表”。遍历每个字符串时只对副本排序，保留原串放入结果；如果直接修改原字符串，最后输出的就不是题目给定的内容。

另一种面试常见签名是 26 个字母的频次数组，序列化成带分隔符的字符串。它能把单词签名从 $O(k \log k)$ 降到 $O(k)$，但键的编码必须避免歧义，例如不能把 [1,11] 与 [11,1] 都直接拼成 "111"。

解题步骤

创建“签名到字符串列表”的哈希表。

对每个原字符串复制字符数组并排序，构造规范签名。

获取或创建签名对应的列表，把原字符串追加进去。

遍历结束后返回哈希表中的所有分组。

以 ["eat","tea","tan","ate","nat","bat"] 为例，前三类签名分别是 aet、ant、abt。eat、tea、ate 进入 aet 桶，tan、nat 进入 ant 桶，bat 单独进入 abt 桶，得到三组答案。

代码实现

// 排序后的字符序列是变位词组的规范签名。
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());
    }
}

// 排序后的字符序列是变位词组的规范签名。
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(\sum k_i \log k_i)$；若统一以最大长度 k 表示，则为 $O(nk \log k)$。

空间复杂度：$O(\sum k_i)$，用于签名和分组列表；不计返回结果时，排序副本与哈希键仍占同量级空间。

关键点总结

分组类题先找等价关系的规范表示，再用“签名 → 桶”聚合，避免 $O(n^2)$ 两两比较。

排序签名简单可靠；26 维频次签名更快，但必须设计无歧义编码。

面试时要主动说明输出顺序未定义。如果题目追加“按首次出现顺序”，需要在首次创建桶时把桶引用放进有序结果。

与 01.02 的关系：01.02 比较两个频次是否相同，本题把这个判定扩展成多个字符串的哈希分组。

易错点总结

用字符集合做键，忽略次数："aab" 与 "abb" 都只含 a、b，却不是变位词。

排序后把签名而不是原串放入桶：样例会输出多个 "aet"，丢失 eat、tea、ate。

频次直接无分隔拼接：不同计数向量可能编码成相同字符串，导致错误合组。

依赖哈希表遍历顺序：Java HashMap 和 Go map 都不保证稳定顺序；只有题目明确不要求顺序时才可直接返回 values。

相似题目

题目	难度	考察点
49. 字母异位词分组	中等	字符计数
242. 有效的字母异位词	简单	字符计数
383. 赎金信	简单	字符计数
387. 字符串中的第一个唯一字符	简单	字符计数
451. 根据字符出现频率排序	中等	字符计数
LCR 032. 有效的字母异位词	简单	字符计数
LCR 033. 字母异位词分组	中等	字符计数
剑指 Offer 50. 第一个只出现一次的字符	简单	字符计数
面试题 01.01. 判定字符是否唯一	简单	字符计数
面试题 01.02. 判定是否互为字符重排	简单	字符计数
面试题 01.04. 回文排列	简单	字符计数