Solution 1Sorted Key
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hashMap = dict()
for word in strs:
key = "".join(sorted(word))
if key not in hashMap:
hashMap[key] = [word]
else:
hashMap[key].append(word)
return hashMap.values()public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String,List<String>> hash_map = new HashMap<>();
for (String word: strs) {
char[] id = word.toCharArray();
Arrays.sort(id);
String wordId = new String(id);
if (!hash_map.containsKey(wordId)) {
hash_map.put(wordId, new ArrayList<String>());
}
hash_map.get(wordId).add(word);
}
return new ArrayList<>(hash_map.values());
}Solution 2Char Count
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hashMap = defaultdict(list)
for word in strs:
key = [0] * 26
for ch in word:
key[ord(ch) - ord('a')] += 1
key = str(key)
hashMap[key].append(word)
return hashMap.values()public List<List<String>> groupAnagrams2(String[] strs) {
Map<String,ArrayList<String>> hash = new HashMap<>();
for(String word: strs) {
char[] count = new char[26];
for(char c: word.toCharArray()) {
count[c-'a']++;
}
String id = String.valueOf(count);
hash.putIfAbsent(id, new ArrayList<String>());
hash.get(id).add(word);
}
return new ArrayList<>(hash.values());
}Solution 3Prime Hash
Python
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
values = {'a':2,'b':3,'c':5,'d':7,'e':11,'f':13,'g':17,'h':19,'i':23,'j':29,'k':31,'l':37,'m':41,'n':43,'o':47,'p':53,'q':59,'r':61,'s':67,'t':71,'u':73,'v':79,'w':83,'x':89,'y':97,'z':101}
hashSet = defaultdict(list)
for word in strs:
h = 1
for ch in word: h *= values[ch]
hashSet[h].append(word)
return hashSet.values()Solution 4Count Signature
Java
public List<List<String>> groupAnagrams3(String[] strs) {
Map<String, ArrayList<String>> map = new HashMap<>();
for (String word: strs) {
int[] count = new int[26];
for (char c: word.toCharArray()) {
count[c - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i: count) {
sb.append(i).append("#");
}
String id = sb.toString();
if(!map.containsKey(id)) {
map.put(id, new ArrayList<String>());
}
map.get(id).add(word);
}
return new ArrayList<List<String>>(map.values());
}