-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathGroupAnagrams.java
More file actions
69 lines (63 loc) · 2.85 KB
/
GroupAnagrams.java
File metadata and controls
69 lines (63 loc) · 2.85 KB
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class GroupAnagrams {
//O(n*n_str*log(n_sr)) time and O(n) space
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<>();
Map<String, Integer> str2Id = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String keyStr = new String(chars);
Integer idInt = str2Id.get(keyStr);
if (idInt == null) {
idInt = str2Id.size();
str2Id.put(keyStr, idInt);
}
if (idInt >= result.size()) {
result.add(new ArrayList<String>());
}
List<String> curGroup = result.get(idInt);
curGroup.add(str);
}
return result;
}
public List<List<String>> groupAnagrams0(String[] strs) {
Map<String, List<String>> anaMap = new LinkedHashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
//This is the costly part since each str could be very long,
//and there could be many strings in the input array.
//Using counting sort instead is better.
//Or simply use the counting array list as key
Arrays.sort(chars);
String sortedStr = new String(chars);
//The following seems to be more costly on OJ than what it stands for.
anaMap.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(anaMap.values());
}
//Convert counting array to a string, similar to using counting sort
//https://discuss.leetcode.com/topic/5460/java-solution-use-hashmap-use-simple-string-uid-as-key
//https://discuss.leetcode.com/topic/33030/java-22-ms-and-20-lines-36-ms-and-11-lines-172-ms-and-9-lines-d
private String getUid(String s) {
int k = 26;
//Each char represents a count for the corresponding letter, assuming that
//the number of occurrence for each letter can fit in 2 bytes.
char[] countings = new char[k];
for (int i = 0; i < s.length(); ++i) {
countings[(int)(s.charAt(i) - 'a')]++;
}
return new String(countings);
}
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> anaMap = new HashMap<>();
for (String str : strs) {
String uid = getUid(str);
anaMap.computeIfAbsent(uid, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(anaMap.values());
}
//Another solution that map each letter to a prime number so that each string
//can be uniquely represented by the product of those prime numbers.
//https://discuss.leetcode.com/topic/12509/o-m-n-algorithm-using-hash-without-sort
//However it could easily overflow.
}