这是我参与11月更文挑战的第17天,活动详情查看:2021最后一次更文挑战
推荐阅读
大家好,我是小魔龙,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]。
遍历完数组,最后从字典中取值即可。
近期评论