-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
49.java
129 lines (118 loc) · 4.16 KB
/
49.java
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
__________________________________________________________________________________________________
6ms
class Solution {
int[] hash = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 67, 71, 83, 89, 101, 107, 109, 113, 127, 131};
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> res = new ArrayList();
Map<Integer, List<String>> map = new HashMap();
for(String s : strs){
int hash = getHash(s);
if(!map.containsKey(hash)){
List<String> group = new ArrayList();
map.put(hash, group);
res.add(group);
}
map.get(hash).add(s);
}
return res;
}
private int getHash(String s){
int hashValue = 1;
for(int i = 0; i < s.length(); i++){
hashValue *= hash[s.charAt(i) - 'a'];
}
return hashValue;
}
}
__________________________________________________________________________________________________
7ms
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map = new HashMap<>();
List<List<String>> anagramList = new ArrayList<>();
for (String str : strs) {
char[] arr = str.toCharArray();
Arrays.sort(arr);
String sorted = new String(arr);
List<String> list = map.get(sorted);
if (list == null) {
list = new ArrayList<>();
map.put(sorted, list);
anagramList.add(list);
}
list.add(str);
}
return anagramList;
}
}
__________________________________________________________________________________________________
8ms
class Solution {
// sort the characters of the string to make them the same
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> res = new ArrayList<>();
if(strs == null || strs.length == 0)
{
return res;
}
Map<String, List<String>> map = new HashMap<String, List<String>>();
for(String tmpStr : strs)
{
char[] tmpArr = tmpStr.toCharArray();
Arrays.sort(tmpArr);
String keyStr = String.valueOf(tmpArr);
if(map.containsKey(keyStr))
{
map.get(keyStr).add(tmpStr);
}
else
{
map.put(keyStr, new ArrayList<>());
map.get(keyStr).add(tmpStr);
}
}
return new ArrayList(map.values());
}
}
__________________________________________________________________________________________________
38392 kb
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(int i=0;i<strs.length;i++){
char[] ch = strs[i].toCharArray();
Arrays.sort(ch);
List<String> nl = map.getOrDefault(new String(ch),new ArrayList<String>());
nl.add(strs[i]);
map.put(new String(ch),nl);
}
List<List<String>> result = new ArrayList<>(map.values());
return result;
}
}
__________________________________________________________________________________________________
38436 kb
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new LinkedList<>();
Map<String, List<String>> map = new HashMap<>();
for(String str : strs)
{
char[] arr = new char[26];
for(int i =0; i<str.length(); i++)
{
arr[str.charAt(i) - 'a']++;
}
String ns = new String(arr);
if(!map.containsKey(ns))
{
List<String> al = new LinkedList<String>();
map.put(ns, al);
}
map.get(ns).add(str);
}
result.addAll(map.values());
return result;
}
}
__________________________________________________________________________________________________