一、题目
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]。
遍历完数组，最后从字典中取值即可。
