The problem of Group Anagrams is a common algorithmic challenge that asks to group a list of strings such that each group consists of anagrams. Two words are considered anagrams if one can be formed by rearranging the letters of the other, i.e., they contain the same characters in the same frequency.
Problem Statement:
Given an array of strings, group the anagrams together.
Input:
- A list of strings.
Output:
- A list of lists, where each inner list contains strings that are anagrams of each other.
Example:
Input:
["eat", "tea", "tan", "ate", "nat", "bat"]
Output:
[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Approach:
The key observation for solving the Group Anagrams problem is that two strings are anagrams if and only if their sorted versions are identical. So, one approach is to sort each string and use the sorted version as a key to group the anagrams.
- Sort each string: By sorting each string, you can generate a unique key for anagrams. For example, the sorted version of
"eat","tea", and"ate"will be"aet". - Use a hash map (or dictionary): Use a hash map (or dictionary) to store these sorted keys as keys and group the original strings as values. This way, all anagrams will be grouped under the same key.
- Output the grouped anagrams: After processing all strings, the values of the hash map will give you the required groups of anagrams.
Algorithm (in pseudocode):
- Initialize an empty dictionary
groupedAnagrams. - Iterate through each string
sin the input list:- Sort the string
sto getsorted_str. - If
sorted_stris not ingroupedAnagrams, add it with an empty list. - Append the original string
stogroupedAnagrams[sorted_str].
- Sort the string
- Convert the values of
groupedAnagramsto a list and return the result.
Complexity Analysis:
- Time Complexity:
- Sorting each string takes O(klogk)O(k \log k)O(klogk), where kkk is the length of the string.
- For nnn strings, the time complexity is O(n⋅klogk)O(n \cdot k \log k)O(n⋅klogk), where nnn is the number of strings and kkk is the average length of a string.
- Space Complexity:
- The space complexity is O(n⋅k)O(n \cdot k)O(n⋅k), where nnn is the number of strings and kkk is the average length of a string (for storing the sorted strings and the resulting groups).
Code Implementations:
1. C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> anagramGroups;
for (string s : strs) {
string sorted_str = s;
sort(sorted_str.begin(), sorted_str.end());
anagramGroups[sorted_str].push_back(s);
}
vector<vector<string>> result;
for (auto& pair : anagramGroups) {
result.push_back(pair.second);
}
return result;
}
int main() {
vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
vector<vector<string>> result = groupAnagrams(strs);
for (auto& group : result) {
for (string word : group) {
cout << word << " ";
}
cout << endl;
}
return 0;
}
2. C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_STR_LEN 100
#define MAX_STRINGS 100
// Function to compare two strings (used by qsort)
int compareStrings(const void *a, const void *b) {
return strcmp(*(const char **)a, *(const char **)b);
}
// Function to sort the characters of a string
void sortString(char *str) {
int len = strlen(str);
qsort(str, len, sizeof(char), compareStrings);
}
int main() {
char *strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
int n = 6;
// Temporary array to store sorted strings
char *sortedStrs[n];
for (int i = 0; i < n; i++) {
sortedStrs[i] = strdup(strs[i]);
sortString(sortedStrs[i]);
}
// Grouping logic can be done manually (using hash maps, or just printing similar sorted strings)
// This is just a simple illustration
printf("Grouped Anagrams:\n");
for (int i = 0; i < n; i++) {
printf("%s\n", strs[i]);
}
return 0;
}
3. Java
import java.util.*;
public class GroupAnagrams {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> anagramGroups = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String sortedStr = new String(chars);
anagramGroups.putIfAbsent(sortedStr, new ArrayList<>());
anagramGroups.get(sortedStr).add(s);
}
return new ArrayList<>(anagramGroups.values());
}
public static void main(String[] args) {
GroupAnagrams solution = new GroupAnagrams();
String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
List<List<String>> result = solution.groupAnagrams(strs);
for (List<String> group : result) {
System.out.println(group);
}
}
}
4. Python
from collections import defaultdict
def group_anagrams(strs):
anagram_groups = defaultdict(list)
for s in strs:
sorted_str = ''.join(sorted(s))
anagram_groups[sorted_str].append(s)
return list(anagram_groups.values())
# Test the function
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
result = group_anagrams(strs)
for group in result:
print(group)
5. C#
using System;
using System.Collections.Generic;
public class GroupAnagrams {
public List<List<string>> GroupAnagramsMethod(string[] strs) {
var anagramGroups = new Dictionary<string, List<string>>();
foreach (string s in strs) {
char[] chars = s.ToCharArray();
Array.Sort(chars);
string sortedStr = new string(chars);
if (!anagramGroups.ContainsKey(sortedStr)) {
anagramGroups[sortedStr] = new List<string>();
}
anagramGroups[sortedStr].Add(s);
}
var result = new List<List<string>>();
foreach (var group in anagramGroups.Values) {
result.Add(group);
}
return result;
}
public static void Main() {
GroupAnagrams solution = new GroupAnagrams();
string[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
var result = solution.GroupAnagramsMethod(strs);
foreach (var group in result) {
foreach (var word in group) {
Console.Write(word + " ");
}
Console.WriteLine();
}
}
}
6. JavaScript
function groupAnagrams(strs) {
const anagramGroups = {};
for (let str of strs) {
const sortedStr = str.split('').sort().join('');
if (!anagramGroups[sortedStr]) {
anagramGroups[sortedStr] = [];
}
anagramGroups[sortedStr].push(str);
}
return Object.values(anagramGroups);
}
// Test the function
const strs = ["eat", "tea", "tan", "ate", "nat", "bat"];
const result = groupAnagrams(strs);
console.log(result);
Summary:
The Group Anagrams problem can be efficiently solved by using sorting or character counting and storing results in a hash map. The sorting method is the most straightforward and commonly used. The time complexity of the solution depends on the time to sort each string, which is O(klogk)O(k \log k)O(klogk), where kkk is the average length of a string.