LeetCode - Group Anagrams
Problem description
Given an array of strings, group anagrams together.
Example:
1
2
3
4
5
6
7
8
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.
Analysis
The initial thought is to use a hash function to group String which is anagrams.
Here’s the code:
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
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<Integer, List<String>> map = new HashMap<>();
for (String s:strs){
int hash = getHashCode(s);
if (!map.containsKey(hash)){
map.put(hash, new ArrayList<>());
}
map.get(hash).add(s);
}
List<List<String>> res = new ArrayList<>();
for (Map.Entry<Integer,List<String>> entry: map.entrySet()){
res.add(entry.getValue());
}
return res;
}
int getHashCode(String s){
int[] alphabet = new int[26];
for(char c:s.toCharArray()){
alphabet[c - 'a']++;
}
int res = 0;
for (int i = 0; i < 26; i++){
res += res * 26 + alphabet[i];
}
return res;
}
}