0%

Leetcode049-GroupAnagrams

Description

Given an array of strings, group anagrams together.

Example

1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

Solution

O(NKlogK)

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
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> res = new ArrayList<>();
if (strs == null || strs.length == 0) return res;

HashMap<String, List<String>> map = new HashMap<>();
for (String st: strs){
char[] chs = st.toCharArray();

String key = "";
Arrays.sort(chs);
key = String.valueOf(chs);

if (map.containsKey(key)){
List<String> tmp = new ArrayList<>(map.get(key));
tmp.add(st);
map.put(key, tmp);
}
else{
List<String> tmp = new ArrayList<>();
tmp.add(st);
map.put(key, tmp);
}
}
return new ArrayList<List<String>>(map.values());
}
}

O(N
K)
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
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();

for (String str : strs) {
String encoded = encode(str);
if (map.containsKey(encoded))
map.get(encoded).add(str);
else {
List<String> list = new LinkedList<>();
list.add(str);
map.put(encoded, list);
}
}

return new ArrayList<List<String>>(map.values());
}

private String encode(String str) {
int[] freq = new int[26];
String spliter = "-";

for (int i = 0; i < str.length(); i++)
freq[str.charAt(i) - 'a']++;

StringBuilder sb = new StringBuilder();
for (int i = 0; i < freq.length; i++)
sb.append(freq[i]).append(spliter);

return sb.toString();
}
}