49 Group Anagrams

1. Question

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

2. Implementation

(1) HashMap + Sort
1
public class Solution {
2
public List<List<String>> groupAnagrams(String[] strs) {
3
List<List<String>> res = new ArrayList<>();
4
5
if (strs == null || strs.length == 0) {
6
return res;
7
}
8
9
Map<String, List<String>> map = new HashMap<>();
10
11
for (String str : strs) {
12
char[] letters = str.toCharArray();
13
Arrays.sort(letters);
14
String key = new String(letters);
15
16
if (!map.containsKey(key)) {
17
map.put(key, new ArrayList<>());
18
}
19
20
map.get(key).add(str);
21
}
22
23
for (String key : map.keySet()) {
24
res.add(map.get(key));
25
}
26
return res;
27
}
28
}
Copied!
(2) HashMap + Count Sort
1
public class Solution {
2
public List<List<String>> groupAnagrams(String[] strs) {
3
List<List<String>> res = new ArrayList<>();
4
5
if (strs == null || strs.length == 0) {
6
return res;
7
}
8
9
Map<String, List<String>> map = new HashMap<>();
10
11
for (String str : strs) {
12
int[] count = new int[256];
13
for (char c : str.toCharArray()) {
14
count[c]++;
15
}
16
17
StringBuilder key = new StringBuilder();
18
for (char c = 0; c < 256; c++) {
19
if (count[c] != 0) {
20
key.append(count[c]);
21
key.append(c);
22
}
23
}
24
25
map.putIfAbsent(key.toString(), new ArrayList<>());
26
map.get(key.toString()).add(str);
27
}
28
29
for (String key : map.keySet()) {
30
res.add(map.get(key));
31
}
32
return res;
33
}
34
}
Copied!

3. Time & Space Complexity

HashMap + Sort: 时间复杂度O( m * nlogn), m是strs的长度, n是strs中最长string的长度,空间复杂度O(mn)
HashMap + Count Sort: 时间复杂度O(mn), 空间复杂度O(mn)
Last modified 2yr ago