题目要求
1
2
3
4
5
6
7
8
9
10
11
| Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note: All inputs will be in lower-case.
|
将含有相同的字母但是排序可能不同的单词分类至不同的数组
思路一：不使用map（超时了）
这里利用了String的API方法toCharArray来对两个单词是否是相同字母组成的进行比较。但是效率较低。这里有重复的无效操作，例如获得当前数组的第一个值并重新计算其对应的有序char数组。而且比较两个char数组的方法造成了三圈循环，带来的O(n3)的时间复杂度
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
35
36
37
38
39
40
41
42
43
44
45
46
| public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new LinkedList<List<String>>();
L1:for(int i = 0 ; i < strs.length ; i++){
String temp = strs[i];
int tempLength = temp.length();
L2:for(int j = 0 ; j<result.size() ; j++){
List<String> currentList = result.get(j);
String currentString = currentList.get(0);
int currentStringLength = currentString.length();
if(currentStringLength>tempLength){
List<String> newResult = new ArrayList<String>();
newResult.add(temp);
result.add(j, newResult);
continue L1;
}else if (currentStringLength<tempLength){
continue L2;
}else{
if(isPermutation(currentString, temp)){
result.get(j).add(temp);
continue L1;
}
}
}
List<String> newResult = new ArrayList<String>();
newResult.add(temp);
result.add(newResult);
}
return result;
}
public boolean isPermutation(String s1, String s2){
if(s1.length() != s2.length()){
return false;
}
char[] s1array = s1.toCharArray();
Arrays.sort(s1array);
char[] s2array = s2.toCharArray();
Arrays.sort(s2array);
for(int i = 0 ; i<s1array.length ; i++){
if(s1array[i] != s2array[i]){
return false;
}
}
return true;
}
|
思路二：利用String.valueof
其实在这里利用Map会减少重复的生成char数组的过程。同时使用String.valueof()方法将char数组转化为String并利用String的API直接比较两个字符串是否相等。通过这种方法效率值提高了不少。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public List<List<String>> groupAnagrams2(String[] strs){
Map<String, List<String>> map = new HashMap<String, List<String>>();
for(String temp : strs){
char[] current = temp.toCharArray();
Arrays.sort(current);
String sortedTemp = String.valueOf(current);
if(!map.containsKey(sortedTemp)){
List<String> tempResult = new ArrayList<String>();
tempResult.add(temp);
map.put(sortedTemp, tempResult);
}else{
map.get(sortedTemp).add(temp);
}
}
return new ArrayList<List<String>>(map.values());
}
|