49.字母异位词分组

LeetCode LeetCode 热题100 数组 哈希表 字符串
发布时间 :
字数:2.7k 阅读 : 评论:
  1. 49.字母异位词分组
    1. 49.1 题目
    2. 49.2 题解
      1. 方法一：排序法
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：计数法（字符频次作为 Key）
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 49.3 代码
    4. 49.4 运行结果

49.字母异位词分组

49.1 题目

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

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 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] 仅包含小写字母

49.2 题解

方法一：排序法

思路

核心观察：一组字母异位词中，每个字符串排序后的结果是一样的。对每个字符串，把它转成字符数组，排序后再转回字符串，作为哈希表的键，把原始字符串加入到该键对应的列表中。最终哈希表的每个 Value，就是一组字母异位词。

核心思想：异位词排序后相同，作为哈希表键分组。

具体步骤：

  1. 创建哈希表，键为排序后的字符串，值为异位词列表。
  2. 遍历每个字符串：
    • 排序后作为键
    • 将原字符串加入对应列表
  3. 返回哈希表的所有值。

举例：对于 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]：

  • "eat" → 排序后 "aet" → 分组 {"aet": ["eat"]}
  • "tea" → 排序后 "aet" → 分组 {"aet": ["eat", "tea"]}
  • "tan" → 排序后 "ant" → 分组 {"aet": [...], "ant": ["tan"]}
  • "ate" → 排序后 "aet" → 分组 {"aet": ["eat", "tea", "ate"], ...}
  • "nat" → 排序后 "ant" → 分组 {"ant": ["tan", "nat"], ...}
  • "bat" → 排序后 "abt" → 分组 {"abt": ["bat"], ...}
  • 结果：[["eat","tea","ate"],["tan","nat"],["bat"]]

复杂度分析

  • 时间复杂度：O(n × k log k)，n 为字符串数量，k 为字符串平均长度。
  • 空间复杂度：O(n × k)，存储所有字符串和排序结果。

代码

// 方法一：排序法
// 核心思路：字母异位词排序后结果相同，因此可以将排序后的字符串作为哈希表的键
// 时间复杂度：O(n * k log k)，其中 n 是字符串数量，k 是字符串平均长度
// 空间复杂度：O(n * k)，需要存储所有字符串的排序结果
// 优点：实现简单，逻辑清晰，适合字符串较短的情况
// 缺点：排序操作有额外的时间开销
static IList<IList<string>> GroupAnagrams1(string[] strs)
{
    // 哈希表：Key = 排序后的字符串 Value = 对应的异位词列表
    Dictionary<string, List<string>> anagramDict = new Dictionary<string, List<string>>();

    foreach (string str in strs)
    {
        // 1. 将字符串转为字符数组并排序（异位词排序后结果一致）
        char[] charArray = str.ToCharArray();
        Array.Sort(charArray);
        string sortedKey = new string(charArray);

        // 2. 尝试获取分组，不存在则创建新分组
        if (!anagramDict.TryGetValue(sortedKey, out List<string> group))
        {
            group = new List<string>();
            anagramDict.Add(sortedKey, group);
        }

        // 3. 将原字符串加入对应分组
        group.Add(str);
    }

    // 4. 转换为要求的返回类型（直接复用哈希表的值集合）
    return new List<IList<string>>(anagramDict.Values);
}

方法二：计数法（字符频次作为 Key）

思路

只包含小写字母，可以用长度为 26 的整型数组统计每个字符出现次数。

对每个字符串：

  1. 建一个 int[26] 计数数组，遍历字符，统计 a~`z` 的频次
  2. 把这 26 个计数拼接成一个字符串，作为哈希表键
  3. 把原始字符串加入到该键对应的列表中

同一组异位词的计数数组一定完全相同，因此会落在同一个桶里。

举个例子：strs = ["eat","tea","tan","ate","nat","bat"]

  • “eat”：计数[1,0,0,…,1,0,…,1]（a,e,t各1次）→ 键”1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0”
  • “tea”：计数相同，落入同一桶
  • “tan”：计数[1,0,0,…,1,0,…,1]（a,n,t各1次）→ 新桶

复杂度分析

  • 时间复杂度：O(n × k)
  • 空间复杂度：O(n × 26)

代码

// 方法二：计数法
// 核心思路：统计每个字符串中 26 个字母的出现次数，将计数数组转为字符串作为哈希表的键
// 时间复杂度：O(n * k)，其中 n 是字符串数量，k 是字符串平均长度
// 空间复杂度：O(n * 26)，计数数组固定为 26 个元素
// 优点：避免排序开销，性能更好，适合字符串较长的情况
// 缺点：实现相对复杂，需要处理计数数组到字符串的转换
static IList<IList<string>> GroupAnagrams2(string[] strs)
{
    // 哈希表：Key = 字符计数拼接字符串 Value = 对应的异位词列表
    Dictionary<string, List<string>> anagramDict = new Dictionary<string, List<string>>();

    foreach (string str in strs)
    {
        // 1. 初始化字符计数数组（仅小写字母，共 26 个）
        int[] charCount = new int[26];
        foreach (char c in str)
        {
            // 计算字符对应索引（'a'->0, 'b'->1 ... 'z'->25）
            charCount[c - 'a']++;
        }

        // 2. 将计数数组转为唯一 Key（用逗号分隔避免计数拼接歧义）
        string countKey = string.Join(",", charCount);

        // 3. 尝试获取分组，不存在则创建新分组
        if (!anagramDict.TryGetValue(countKey, out List<string> group))
        {
            group = new List<string>();
            anagramDict.Add(countKey, group);
        }

        // 4. 将原字符串加入对应分组
        group.Add(str);
    }

    // 5. 转换为要求的返回类型
    return new List<IList<string>>(anagramDict.Values);
}

49.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
        // 字母异位词是由重新排列源单词的所有字母得到的一个新单词。

        // 示例 1:
        // 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
        // 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

        // 示例 2:
        // 输入: strs = [""]
        // 输出: [[""]]

        // 示例 3:
        // 输入: strs = ["a"]
        // 输出: [["a"]]

        // 提示：
        // 1 <= strs.length <= 104
        // 0 <= strs[i].length <= 100
        // strs[i] 仅包含小写字母

        #endregion

        #region 测试

        // 示例 1
        string[] strs1 = { "eat", "tea", "tan", "ate", "nat", "bat" };
        IList<IList<string>> result11 = GroupAnagrams1(strs1);
        IList<IList<string>> result12 = GroupAnagrams2(strs1);
        Console.WriteLine("示例1 方法1 输出：");
        foreach (var group in result11)
        {
            Console.WriteLine($"[{string.Join(",", group)}]");
        }

        Console.WriteLine("示例1 方法2 输出：");
        foreach (var group in result12)
        {
            Console.WriteLine($"[{string.Join(",", group)}]");
        }

        // 示例 2
        string[] strs2 = { "" };
        IList<IList<string>> result21 = GroupAnagrams1(strs2);
        IList<IList<string>> result22 = GroupAnagrams2(strs2);
        Console.WriteLine("示例2 方法1 输出：");
        foreach (var group in result21)
        {
            Console.WriteLine($"[{string.Join(",", group)}]");
        }

        Console.WriteLine("示例2 方法2 输出：");
        foreach (var group in result22)
        {
            Console.WriteLine($"[{string.Join(",", group)}]");
        }

        // 示例 3
        string[] strs3 = { "a" };
        IList<IList<string>> result31 = GroupAnagrams1(strs3);
        IList<IList<string>> result32 = GroupAnagrams2(strs3);
        Console.WriteLine("示例3 方法1 输出：");
        foreach (var group in result31)
        {
            Console.WriteLine($"[{string.Join(",", group)}]");
        }

        Console.WriteLine("示例3 方法2 输出：");
        foreach (var group in result32)
        {
            Console.WriteLine($"[{string.Join(",", group)}]");
        }

        #endregion
    }

    #region 答案

    // 方法一：排序法
    // 核心思路：字母异位词排序后结果相同，因此可以将排序后的字符串作为哈希表的键
    // 时间复杂度：O(n * k log k)，其中n是字符串数量，k是字符串平均长度
    // 空间复杂度：O(n * k)，需要存储所有字符串的排序结果
    // 优点：实现简单，逻辑清晰，适合字符串较短的情况
    // 缺点：排序操作有额外的时间开销
    static IList<IList<string>> GroupAnagrams1(string[] strs)
    {
        // 哈希表：Key=排序后的字符串 Value=对应的异位词列表 
        Dictionary<string, List<string>> anagramDict = new Dictionary<string, List<string>>();

        foreach (string str in strs)
        {
            // 1. 将字符串转为字符数组并排序（异位词排序后结果一致） 
            char[] charArray = str.ToCharArray();
            Array.Sort(charArray);
            string sortedKey = new string(charArray);

            // 2. 尝试获取分组，不存在则创建新分组 
            if (!anagramDict.TryGetValue(sortedKey, out List<string> group))
            {
                group = new List<string>();
                anagramDict.Add(sortedKey, group);
            }

            // 3. 将原字符串加入对应分组 
            group.Add(str);
        }

        // 4. 转换为要求的返回类型（直接复用哈希表的值集合） 
        return new List<IList<string>>(anagramDict.Values);
    }

    // 方法二：计数法
    // 核心思路：统计每个字符串中26个字母的出现次数，将计数数组转为字符串作为哈希表的键
    // 时间复杂度：O(n * k)，其中n是字符串数量，k是字符串平均长度
    // 空间复杂度：O(n * 26)，计数数组固定为26个元素
    // 优点：避免排序开销，性能更好，适合字符串较长的情况
    // 缺点：实现相对复杂，需要处理计数数组到字符串的转换
    static IList<IList<string>> GroupAnagrams2(string[] strs)
    {
        // 哈希表：Key=字符计数拼接字符串 Value=对应的异位词列表 
        Dictionary<string, List<string>> anagramDict = new Dictionary<string, List<string>>();

        foreach (string str in strs)
        {
            // 1. 初始化字符计数数组（仅小写字母，共26个） 
            int[] charCount = new int[26];
            foreach (char c in str)
            {
                // 计算字符对应索引（'a'->0, 'b'->1 ... 'z'->25） 
                charCount[c - 'a']++;
            }

            // 2. 将计数数组转为唯一Key（用逗号分隔避免计数拼接歧义，如11和1+1） 
            string countKey = string.Join(",", charCount);

            // 3. 尝试获取分组，不存在则创建新分组 
            if (!anagramDict.TryGetValue(countKey, out List<string> group))
            {
                group = new List<string>();
                anagramDict.Add(countKey, group);
            }

            // 4. 将原字符串加入对应分组 
            group.Add(str);
        }

        // 5. 转换为要求的返回类型 
        return new List<IList<string>>(anagramDict.Values);
    }

    #endregion
}

49.4 运行结果

示例1 方法1 输出：
[eat,tea,ate]
[tan,nat]
[bat]
示例1 方法2 输出：
[eat,tea,ate]
[tan,nat]
[bat]
示例2 方法1 输出：
[]
示例2 方法2 输出：
[]
示例3 方法1 输出：
[a]
示例3 方法2 输出：
[a]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏