AlgoPressAppearance
0049-字母异位词分组
题目描述
https://leetcode.cn/problems/group-anagrams
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 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]仅包含小写字母
思路1:排序+哈希表【ME】
字母排序，那么 异位词 的排序后结果应该相同 使用字典排重，最后再输出到 list
csharp
public class Solution {
private string SortWord(string str){
char[] arr = str.ToCharArray();
Array.Sort(arr);
return new string(arr);
}
public IList<IList<string>> GroupAnagrams(string[] strs) {
Dictionary<string, List<string>> dict = new Dictionary<string,List<string>>();
for(int i=0; i<strs.Length; i++){
string key = SortWord(strs[i]);
if(!dict.ContainsKey(key)){
List<string> list = new List<string>();
list.Add(strs[i]);
dict.Add(key,list);
}
else{
dict[key].Add(strs[i]);
}
}
//输出结果
List<IList<string>> result = new List<IList<string>>();
foreach(string key in dict.Keys){
result.Add(dict[key]);
}
return result;
}
}
思路2:其他Key+哈希表【官方】
思路1中，使用了排序后的字符串 做为hash表的 key。 还可以使用其他方法得到 key，比如统计每个字符出现的次数作为key。
csharp
public class Solution {
private string GetCountKey(string str){
int[] counts = new int[26];
int length = str.Length;
for (int i = 0; i < length; i++) {
counts[str[i] - 'a']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.Append((char) ('a' + i));
sb.Append(counts[i]);
}
}
return sb.ToString();
}
public IList<IList<string>> GroupAnagrams(string[] strs) {
Dictionary<string, List<string>> dict = new Dictionary<string,List<string>>();
for(int i=0; i<strs.Length; i++){
string key = GetCountKey(strs[i]);
if(!dict.ContainsKey(key)){
List<string> list = new List<string>();
list.Add(strs[i]);
dict.Add(key,list);
}
else{
dict[key].Add(strs[i]);
}
}
//输出结果
List<IList<string>> result = new List<IList<string>>();
foreach(string key in dict.Keys){
result.Add(dict[key]);
}
return result;
}
}