☆打卡算法☆LeetCode 49、字母异位词分组 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个字符串数组，返回 字母异位词 列表。”

题目链接：

来源：力扣（LeetCode）

链接：49. 字母异位词分组 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

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

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

二、解题

1、思路分析

首先分析题意，字母异位词，是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

这就意味着新旧两个字符串互为字母异位词，因为两个字符串包含的字母相同，同一组字母异位词中的字符串具有相同点。

可以使用相同点作为一组字母异位词的标志，使用哈希表来保存每一组字母异位词，然后遍历每个字符串，得到该字符串中相同点，将当前字符串加入该字母异位词中，遍历完之后，哈希表中每个键值对应即为一组字母异位词。

2、代码实现

代码参考：

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
            var dic = new Dictionary<string, IList<string>>();
            IList<IList<string>> res = new List<IList<string>>();
            for (int i = 0; i < strs.Length; i++)
            {
                char[] a = strs[i].ToArray();
                Array.Sort(a);
                string str = String.Join("", a.Select(x => x.ToString()).ToArray());
                if (dic.ContainsKey(str))
                {
                    dic[str].Add(strs[i]);
                }
                else
                {
                    dic[str] = new List<string> { strs[i] };
                }

            }
            foreach (var item in dic.Keys)
            {
                res.Add(dic[item]);
            }
            return res;
    }
}

3、时间复杂度

时间复杂度 ： O(nk log k)

其中n是字符串数组的数量，k是字符串数组中最长字符串的长度，需要遍历n个字符串，对于每个字符串需要O(k log k)的时间进行排序，以及O(1)的时间更新哈希表，所以总时间复杂度是O(nk log k)。

空间复杂度： O(nk)

其中n是字符串数组的数量，k是字符串数组中最长字符串的长度。

三、总结

总体思路就是使用字典，将相同点存入字典中，进行遍历。

在遍历过程中将 每个字符串进行排序比较，排序的字符串作为key值，Value为strs[i]。

遍历完数组，最后从字典中取值即可。