Description
Given an array of strings, group anagrams together.
Example
1 | Input: ["eat", "tea", "tan", "ate", "nat", "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
27class 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(NK)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
32class 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();
}
}