字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
1
2
| 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
|
示例 2:
1
2
| 输入: strs = [""]
输出: [[""]]
|
示例 3:
1
2
| 输入: strs = ["a"]
输出: [["a"]]
|
解法一：排序
将字符串数组中的元素，进行排序，根据排序后的值作为键，原始值存储到map中，返回map中的值就是结果。
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String ,LinkedList<String>> map = new HashMap<>();
for (int i = 0;i<strs.length;i++){
char[] chars = strs[i].toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
if (!map.containsKey(key)){
map.put(key,new LinkedList<>());
}
map.get(key).add(strs[i]);
}
return new LinkedList<>(map.values());
}
}
|
解法：计数
对每个字符串计数得到该字符串的计数数组，对于计数数组相同的字符串，就互为异位词。
因为数组类型没有重写 hashcode() 和 equals() 方法，因此不能直接作为 HashMap 的 Key 进行聚合，那么我们就 把这个数组手动编码变成字符串就行了。
比如将 [b,a,a,a,b,c] 编码成 a3b2c1，使用编码后的字符串作为 HashMap 的 Key 进行聚合。
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for (int i = 0;i<strs.length;i++){
int count[] = new int[26];
char[] chars = strs[i].toCharArray();
for (int j = 0;j<chars.length;j++){
count[chars[j]-'a']++;
}
StringBuffer stringBuffer = new StringBuffer();
for (int j = 0;j<26;j++){
if (count[j]!=0){
stringBuffer.append((char) j+'a');
stringBuffer.append(count[j]);
}
}
String key = stringBuffer.toString();
List<String> list = map.getOrDefault(key, new LinkedList<>());
list.add(strs[i]);
map.put(key,list);
}
return new LinkedList<List<String>>(map.values());
}
}
|