Group Anagrams
Given a sequence of words, print all anagrams together – Anagrams Group Problem
Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.
An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.
Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]
Output: [["x"]]
Output: [[""]]
Constraints:
- 1 <= strs.length <= 1000
- 0 <= strs[i].length <= 100
- strs[i] is made up of lowercase English letters.
Given a sequence of words, print all anagrams together - Anagrams Group Solution
Recommendation – You should aim for a solution with O(m * n) time and O(m) space, where m is the number of strings and n is the length of the longest string.
Hints for solving problems
Hint 1 :
A naive solution would be to sort each string and group them using a hash map. This would be an O(m * nlogn) solution. Though this solution is acceptable, can you think of a better way without sorting the strings?
Hint 2:
By the definition of an anagram, we only care about the frequency of each character in a string. How is this helpful in solving the problem?
Hint 3:
We can simply use an array of size O(26), since the character set is a through z (26 continuous characters), to count the frequency of each character in a string. Then, we can use this array as the key in the hash map to group the strings.
There are mainly 2 approach to solve this problem
- Sorting Method
- Hash Table Method
1. Sorting Method
This method sort each word in the list, use the sorted word as a key in a hash map, and group words with the same sorted key together.
- Time complexity: O(m*nlog n)
- Space complexity: O(m*n)
where m is the number of strings and n is the length of the longest string.
Code
class Solution {
public:
vector> groupAnagrams(vector& strs) {
unordered_map> res;
for (const auto& s : strs) {
string sortedS = s;
sort(sortedS.begin(), sortedS.end());
res[sortedS].push_back(s);
}
vector> result;
for (auto& pair : res) {
result.push_back(pair.second);
}
return result;
}
};
public class Solution {
public List> groupAnagrams(String[] strs) {
Map> res = new HashMap<>();
for (String s : strs) {
char[] charArray = s.toCharArray();
Arrays.sort(charArray);
String sortedS = new String(charArray);
res.putIfAbsent(sortedS, new ArrayList<>());
res.get(sortedS).add(s);
}
return new ArrayList<>(res.values());
}
}
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list)
for s in strs:
sortedS = ''.join(sorted(s))
res[sortedS].append(s)
return list(res.values())
class Solution {
/**
* @param {string[]} strs
* @return {string[][]}
*/
groupAnagrams(strs) {
const res = {};
for (let s of strs) {
const sortedS = s.split('').sort().join('');
if (!res[sortedS]) {
res[sortedS] = [];
}
res[sortedS].push(s);
}
return Object.values(res);
}
}
2. Hash Table Method
This method use a hash table with a character frequency count as the key to group words that have the same character counts into the same group.
- Time complexity: O(m*n)
- Space complexity: O(m)
where m is the number of strings and n is the length of the longest string.
Code
class Solution {
public:
vector> groupAnagrams(vector& strs) {
unordered_map> res;
for (const auto& s : strs) {
vector count(26, 0);
for (char c : s) {
count[c - 'a']++;
}
string key = to_string(count[0]);
for (int i = 1; i < 26; ++i) {
key += ',' + to_string(count[i]);
}
res[key].push_back(s);
}
vector> result;
for (const auto& pair : res) {
result.push_back(pair.second);
}
return result;
}
};
public class Solution {
public List> groupAnagrams(String[] strs) {
Map> res = new HashMap<>();
for (String s : strs) {
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
String key = Arrays.toString(count);
res.putIfAbsent(key, new ArrayList<>());
res.get(key).add(s);
}
return new ArrayList<>(res.values());
}
}
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
res[tuple(count)].append(s)
return list(res.values())
class Solution {
/**
* @param {string[]} strs
* @return {string[][]}
*/
groupAnagrams(strs) {
const res = {};
for (let s of strs) {
const count = new Array(26).fill(0);
for (let c of s) {
count[c.charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
}
const key = count.join(',');
if (!res[key]) {
res[key] = [];
}
res[key].push(s);
}
return Object.values(res);
}
}
