Problem: 49. 字母异位词分组
思路
字母异位词排序后是同一个字符串,用Hash表存贮排序后的字符串为键,源字符串为值(List),
解题方法
- strs[i]转化为Char类型的Array
- 转化后的字符串排序
- 得到排序后的字符串key = new string(charArray);
- 在dic中,TryAdd这个键(排序后的字符串)
- 在dic对应键的值Add源字符串strs[i]
复杂度
时间复杂度:
添加时间复杂度, 示例： $O(n)$
空间复杂度:
添加空间复杂度, 示例： $O(n)$
Code
[]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class Solution {
public IList<IList<string>> GroupAnagrams(string[] strs) {
Dictionary<string,List<string>> dic = new Dictionary<string,List<string>>();
for(int i = 0; i < strs.Length; i ++) {
char[] charArray = strs[i].ToCharArray();
Array.Sort(charArray);
string key = new string(charArray);
dic.TryAdd(key,new List<string>());
dic[key].Add(strs[i]);
}
return new List<IList<string>>(dic.Values);
}
}
|