三刷 08/2022
Version #2 Sort the strings
Time O(N*LlogL)
Space O(NL) - we need to store all strings in the map
Runtime: 9 ms, faster than 89.54% of Java online submissions for Group Anagrams.
Memory Usage: 55.8 MB, less than 60.06% of Java online submissions for Group Anagrams.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(str);
}
return new ArrayList<>(map.values());
}
}
Version #3 Use chararray to count
Time O(NL)
Space O(NL)
Runtime: 6 ms, faster than 99.41% of Java online submissions for Group Anagrams.
Memory Usage: 46.4 MB, less than 87.12% of Java online submissions for Group Anagrams.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] count = new char[26];
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
String key = String.valueOf(count);
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(str);
}
return new ArrayList<>(map.values());
}
}
Integer 2,147,483,647
| char | 2 byte | 0 to 65,536 (unsigned) |
char is about 60 thousand
Use List<Integer> as the hashkey
查了一下int[] 在hash的时候必须是exact the same object
但是List<Integer> if two lists have the same elements, they will have the same hashcode
所以要用list<Integer> 作为key
reset的时候可以用Arrays.fill(arr, 0);
int[]转化list的时候可以用 Arrays.asList()
但是自己写的for循环在一次同时做了这两件事，感觉更好一点
6.18 %
效率明显不如version#2
应该是对List<Integer> 的hashing 很慢
进化成version #3
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return null;
// key-List<Integer>, value-List<String>
// key is the count of each character of each string
Map<List<Integer>, List<String>> map = new HashMap<>();
int[] count = new int[26]; // all lower case
for (String str : strs) {
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
List<Integer> key = new ArrayList<>();
for (int j = 0; j < count.length; j++) {
// add to key and reset to zero
key.add(count[j]);
count[j] = 0;
}
if (!map.containsKey(key)) map.put(key, new ArrayList<>());
map.get(key).add(str);
}
List<List<String>> result = new ArrayList<>();
for (List<String> list : map.values()) {
list.sort(null);
result.add(list);
}
return result;
}
}
Version #3
二刷
用char array 作为count 数组
然后直接把char array 变成String
这样我们用一个Object-String取代了一个array
提高了hashing的效率
44.96 %
原code看着简洁但是要两次hashing
//if (!map.containsKey(key)) map.put(key, new ArrayList<>());
//map.get(key).add(str);
把map.get(key) cache住以后只需要一次hashing，用空间换时间
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return null;
// key-List<Integer>, value-List<String>
// key is the count of each character of each string
Map<String, List<String>> map = new HashMap<>();
char[] count = new char[26]; // all lower case
List<String> temp = null;
for (String str : strs) {
Arrays.fill(count, (char)0);
for (int i = 0; i < str.length(); i++) {
count[str.charAt(i) - 'a']++;
}
String key = String.valueOf(count);
temp = map.get(key);
if (temp == null) {
temp = new ArrayList<>();
temp.add(str);
map.put(key, temp);
} else {
temp.add(str);
}
}
List<List<String>> result = new ArrayList<>();
for (List<String> list : map.values()) {
list.sort(null);
result.add(list);
}
return result;
}
}
一刷（还是version #3）
挺好的这道题 很多值得学习的地方
有空再多做做
Time O(inputSize * aveArrayLength)
44.17 %
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return new ArrayList<>();
Map<String, List<String>> map= new HashMap<>();
char[] array = new char[26];
for (String str : strs) {
Arrays.fill(array, (char)0);
for (int i = 0; i < str.length(); i++) {
array[str.charAt(i) - 'a']++;
}
String hash = new String(array);
if (map.containsKey(hash)) {
map.get(hash).add(str);
} else {
List<String> temp = new ArrayList<>();
temp.add(str);
map.put(hash, temp);
}
}
return new ArrayList<List<String>>(map.values());
}
}
Version #2
对于anagram来说invariant是它们按char顺序sort之后的string
用这个string作为key可以把所有的string归类
avage string length -> len
array size -> n
O(n len log(len) + listSize * averagelistLength)
37.71 %
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return null;
List<List<String>> result = new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String curr = String.valueOf(chars);
if (!map.containsKey(curr)) map.put(curr, new ArrayList<>());
map.get(curr).add(str);
}
for (List<String> list : map.values()) {
list.sort(null);
result.add(list);
}
return result;
}
}
No comments:
Post a Comment