49 Group Anagrams

Search…
49 Group Anagrams
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)
Sort
75 Sort Colors
Last modified 2yr ago
Copy link
Contents
49. Group Anagrams
1. Question
2. Implementation
3. Time & Space Complexity
49. Group Anagrams​

1. Question

2. Implementation

3. Time & Space Complexity

49. Group Anagrams
