难度中等 2026-06-24 哈希表字符串排序

字母异位词分组：用排序签名把同类字符串聚到一起

摘要：这道题要求把一组字符串按“字母异位词”关系分组，核心不在暴力两两比较，而在为每个字符串构造一个可以代表其字符组成的签名。最直观的做法是把字符串排序后作为哈希表 key，所有排序结果相同的字符串自然落入同一组。读完本文，你会掌握分组类哈希题的通用写法，并理解什么时候可以把排序签名优化成计数签名。

一、题意转述

给定一个字符串数组，需要把互为字母异位词的字符串放到同一个分组里。

所谓字母异位词，是指两个字符串使用的字符及每个字符出现次数完全相同，只是排列顺序不同。例如 eat、tea、ate 属于同一组，因为它们都由一个 a、一个 e、一个 t 组成。

这类题通常不要求分组之间的顺序，也不要求每个分组内部保持固定顺序；只要同组关系正确即可。常见接口可以写成：

public IList<IList<string>> GroupAnagrams(string[] strs)

影响算法选择的关键约束是：字符串数量和单个字符串长度都可能不小，不能对每两个字符串都做一次异位词判断。

二、关键观察

两个字符串是否互为字母异位词，取决于“字符多重集合”，而不是原始排列顺序。

换句话说：

eat 排序后是 aet
tea 排序后是 aet
tan 排序后是 ant

排序后的字符串可以当作这个单词的“标准形”。只要标准形相同，原字符串就属于同一个异位词分组。

这就是本题的核心观察：不要比较字符串之间的关系，而是先把每个字符串映射到一个稳定签名，再按签名聚合。

三、解题思路

使用一个哈希表：

key：字符串的签名，最直接是排序后的结果；
value：所有拥有这个签名的原始字符串列表。

处理每个字符串时：

把字符串转成字符数组；
对字符数组排序；
用排序后的字符串作为 key；
把原字符串加入 Dictionary 对应的列表。

遍历结束后，哈希表中的每个 value 就是一个答案分组。

如果输入只包含小写英文字母，还可以用长度为 26 的计数数组作为签名。例如 aab 可以表示成 a:2, b:1。计数签名能把单词内部排序的 O(k log k) 降为 O(k)，但代码稍微啰嗦一些。教学上通常先掌握排序签名，再理解计数签名优化。

四、算法推导

假设当前处理到字符串 word。

如果直接拿它和已有分组里的代表字符串逐个比较，那么最坏情况下会退化成大量重复判断。更好的做法是让每个字符串自己算出“应该去哪个桶”。

定义函数：

signature(word) = sort(word)

对于任意两个字符串 a 和 b：

如果 signature(a) == signature(b)，说明二者字符组成完全相同，应该在同一组；
如果 signature(a) != signature(b)，说明至少有某个字符的数量不同，不能在同一组。

因此，signature 可以作为哈希分组的 key。

整个流程如下：

flowchart LR
    A[原始字符串数组] --> B[逐个字符串计算签名]
    B --> C{哈希表中是否已有该签名}
    C -- 有 --> D[加入已有分组]
    C -- 没有 --> E[创建新分组]
    D --> F[输出所有分组]
    E --> F

flowchart LR
    A[原始字符串数组] --> B[逐个字符串计算签名]
    B --> C{哈希表中是否已有该签名}
    C -- 有 --> D[加入已有分组]
    C -- 没有 --> E[创建新分组]
    D --> F[输出所有分组]
    E --> F

flowchart LR
    A[原始字符串数组] --> B[逐个字符串计算签名]
    B --> C{哈希表中是否已有该签名}
    C -- 有 --> D[加入已有分组]
    C -- 没有 --> E[创建新分组]
    D --> F[输出所有分组]
    E --> F

这里的正确性来自一个简单不变量：遍历过程中，哈希表中每个 key 对应的列表，始终只包含签名相同的字符串；而签名相同等价于互为字母异位词。

五、C# 实现

using System;
using System.Collections.Generic;

public class Solution
{
    public IList<IList<string>> GroupAnagrams(string[] strs)
    {
        var groups = new Dictionary<string, List<string>>(StringComparer.Ordinal);

        foreach (var word in strs)
        {
            char[] chars = word.ToCharArray();
            Array.Sort(chars);
            string key = new string(chars);

            if (!groups.TryGetValue(key, out var list))
            {
                list = new List<string>();
                groups[key] = list;
            }

            list.Add(word);
        }

        var result = new List<IList<string>>();
        foreach (var group in groups.Values)
        {
            result.Add(group);
        }

        return result;
    }
}

如果想用计数签名优化，可以把 key 的构造改成下面这样：

using System.Text;

private static string BuildCountKey(string word)
{
    int[] counts = new int[26];

    foreach (char c in word)
    {
        counts[c - 'a']++;
    }

    var builder = new StringBuilder();
    for (int i = 0; i < 26; i++)
    {
        builder.Append('#');
        builder.Append(counts[i]);
    }

    return builder.ToString();
}

这里必须加分隔符 #。如果直接拼接数字，[1, 11] 和 [11, 1] 这类计数组合可能产生歧义；加分隔符后签名才是可靠的。

六、复杂度分析

设字符串数量为 n，单个字符串的平均长度为 k。

排序签名写法：

时间复杂度：O(n * k log k)，每个字符串都需要排序；
空间复杂度：O(n * k)，哈希表保存分组结果和签名字符串。

计数签名写法：

时间复杂度：O(n * (k + 26))，如果只包含小写英文字母，可以近似看成 O(n * k)；
空间复杂度：O(n * k)，结果本身仍然需要保存所有字符串。

面试或刷题时，排序签名通常已经足够清晰；如果题目强调字符串很长、字符集固定且较小，再主动提计数签名优化。

七、易错点

不要用字符集合当 key。集合只记录字符是否出现，不记录出现次数，ab 和 aabb 会被误判为同类。
不要手写字符串拼接构造计数 key 而不加分隔符，数字边界不清会产生冲突。
不要假设答案顺序固定。很多评测只关心分组内容，不关心分组排列；本地调试时不要被输出顺序干扰。
C# 中 Dictionary<string, List<string>> 的 value 类型不能直接作为 IList<IList<string>> 返回，需要重新装入 List<IList<string>>。
如果输入可能包含非小写英文字母，计数数组写法需要扩展字符集；排序签名对一般字符更省心。

八、同类经典题

8.1 有效的字母异位词

相似点：仍然判断两个字符串是否拥有完全相同的字符组成。

变化点：不需要分组，只需要返回两个字符串是否互为异位词。

迁移方式：主问题里“构造签名再比较 key”的思路可以简化成“统计字符次数再抵消”。如果两个字符串长度不同，直接返回 false。

public class Solution
{
    public bool IsAnagram(string s, string t)
    {
        if (s.Length != t.Length)
        {
            return false;
        }

        int[] counts = new int[26];

        foreach (char c in s)
        {
            counts[c - 'a']++;
        }

        foreach (char c in t)
        {
            counts[c - 'a']--;
            if (counts[c - 'a'] < 0)
            {
                return false;
            }
        }

        return true;
    }
}

复杂度：时间复杂度 O(n)，空间复杂度 O(1)，其中字符集固定为 26 个小写英文字母。

8.2 找到字符串中所有字母异位词

相似点：仍然围绕“字符计数是否相同”判断异位词。

变化点：这次不是在数组里分组，而是在长字符串 s 中找出所有长度等于 p 且与 p 互为异位词的子串起点。

迁移方式：主问题的计数签名思想可以迁移成滑动窗口。维护一个长度为 p.Length 的窗口，让窗口字符计数和目标字符计数保持同步比较。

using System.Collections.Generic;

public class Solution
{
    public IList<int> FindAnagrams(string s, string p)
    {
        var result = new List<int>();
        if (s.Length < p.Length)
        {
            return result;
        }

        int[] need = new int[26];
        int[] window = new int[26];

        foreach (char c in p)
        {
            need[c - 'a']++;
        }

        for (int right = 0; right < s.Length; right++)
        {
            window[s[right] - 'a']++;

            int left = right - p.Length;
            if (left >= 0)
            {
                window[s[left] - 'a']--;
            }

            if (right >= p.Length - 1 && SameCounts(need, window))
            {
                result.Add(right - p.Length + 1);
            }
        }

        return result;
    }

    private static bool SameCounts(int[] a, int[] b)
    {
        for (int i = 0; i < 26; i++)
        {
            if (a[i] != b[i])
            {
                return false;
            }
        }

        return true;
    }
}

复杂度：时间复杂度 O(26 * n)，可视为 O(n)；空间复杂度 O(1)。

8.3 最小覆盖子串

相似点：都要统计字符出现次数，并根据计数关系判断当前字符串片段是否满足要求。

变化点：这里不是要求字符次数完全相等，而是要求窗口覆盖目标字符串中的全部字符，且窗口长度尽量短。

迁移方式：从“固定长度窗口比较计数”升级为“可变长度窗口维护满足状态”。右指针扩张窗口，满足覆盖后左指针尽量收缩。

using System.Collections.Generic;

public class Solution
{
    public string MinWindow(string s, string t)
    {
        if (t.Length == 0 || s.Length < t.Length)
        {
            return string.Empty;
        }

        var need = new Dictionary<char, int>();
        foreach (char c in t)
        {
            need[c] = need.TryGetValue(c, out int count) ? count + 1 : 1;
        }

        var window = new Dictionary<char, int>();
        int valid = 0;
        int left = 0;
        int bestStart = 0;
        int bestLength = int.MaxValue;

        for (int right = 0; right < s.Length; right++)
        {
            char add = s[right];
            if (need.ContainsKey(add))
            {
                window[add] = window.TryGetValue(add, out int count) ? count + 1 : 1;
                if (window[add] == need[add])
                {
                    valid++;
                }
            }

            while (valid == need.Count)
            {
                int length = right - left + 1;
                if (length < bestLength)
                {
                    bestLength = length;
                    bestStart = left;
                }

                char remove = s[left];
                left++;

                if (need.ContainsKey(remove))
                {
                    if (window[remove] == need[remove])
                    {
                        valid--;
                    }

                    window[remove]--;
                }
            }
        }

        return bestLength == int.MaxValue
            ? string.Empty
            : s.Substring(bestStart, bestLength);
    }
}

复杂度：时间复杂度 O(n + m)，空间复杂度 O(c)，其中 c 是参与统计的字符种类数。

九、复盘总结

这道题的本质是“把对象归一化后再分组”。一旦能为每个字符串构造稳定签名，问题就从复杂的两两关系判断，变成了非常直接的哈希表聚合。

排序签名是最容易写对的版本，适合优先掌握；计数签名则适合字符集固定、字符串较长时进一步优化。以后遇到“同类归并”“去重分类”“忽略顺序比较内容”的题，都可以先问自己：能不能为每个元素设计一个稳定、无歧义的 key？