题目描述
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
1
2
| 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
|
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我的题解
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
28
29
30
31
32
33
34
| import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result =new ArrayList<>();
List<String> src=new LinkedList<>();
for(String str : strs)
{
src.add(str);
}
for(int i=0;i<src.size();i++)
{
char[] ch1=src.get(i).toCharArray();
Arrays.sort(ch1);
List<String> list=new ArrayList<>();
for(int j=i+1;j<src.size();j++)
{
char[] ch2=src.get(j).toCharArray();
Arrays.sort(ch2);
if(Arrays.equals(ch1,ch2)) {
list.add(src.get(j));
src.remove(j);
j--;
}
}
list.add(src.get(i));
src.remove(i);
i--;
result.add(list);
}
return result;
}
}
|
先说结论由于我的此题设计的算法复杂度过高，测试后面时出现大数据就超时了，不正确。我的具体思路就是将每个字符串转换成字符数组，然后再将字符数组排序，如果两个字符数组相等，则将它们放在同一个数组表里面，放进去以后将原来的字符串数组中的对应元素删除，由于此时删除元素后每一个元素的下标要变，故记得进行i–和j–。记得一组字符组排序相同的元素存完了后要新new一个来存储新的一组排序后字符数组相同的元素，不要调用clear清除原来的数组表，因为表add存储的是数组表list的地址,而clean清除的是地址里的元素，如果使用clear而不新new的话原来存在表add的·元素会都变成空。
大神题解
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
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> lists = new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
String change = change(strs[i]);
if (map.containsKey(change)) {
map.get(change).add(strs[i]);
} else {
List<String> l = new ArrayList<>();
l.add(strs[i]);
map.put(change, l);
}
}
for (Map.Entry<String, List<String>> entry : map.entrySet()) {
lists.add(entry.getValue());
}
return lists;
}
public String change(String s) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
return String.valueOf(chars);
}
}
|
来自：https://leetcode.cn/problems/group-anagrams/solution/kan-wo-yi-ju-hua-ac-zi-mu-yi-wei-ci-fen-yrnis/中的评论区。
可以看出大神利用了map来优化算法，map中键值为字符串和表,定义一个将字符串排序的函数，如果键值中有排序后的字符串，则将为排序前的字符串放入值中的表，如果没有，就新建一个键值对，这样永map来识别相同的排序后字符串就大大优化了效率。