To create an anagram, one rearranges the letters of a word to form a new word, like transforming "listen" into "silent". When organizing anagrams within a set of strings, the objective is to cluster together all strings that are anagrams of one another.
Example 1:
Below is a code snippet in C++ that demonstrates how to implement a hash table to group anagrams:
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hashTable;
for (string& s : strs) {
string sortedStr = s;
sort(sortedStr.begin(), sortedStr.end());
hashTable[sortedStr].push_back(s);
}
vector<vector<string>> groupedAnagrams;
for (auto& pair : hashTable) {
groupedAnagrams.push_back(pair.second);
}
return groupedAnagrams;
}
int main() {
vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};
vector<vector<string>> grouped = groupAnagrams(words);
for (const auto& group : grouped) {
cout << "[ ";
for (const string& word : group) {
cout << word << " ";
}
cout << "]" << endl;
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <string>
// Function to group anagrams
void groupAnagrams(std::vector<std::string>& strs) {
std::unordered_map<std::string, std::vector<std::string>>hashTable;
for (const auto&str : strs) {
std::string temp = str;
// Sort the string to form a key
std::sort(temp.begin(), temp.end());
hashTable[temp].push_back(str);
}
strs.clear();
for (const auto& [key, value] :hashTable) {
for (const auto&str : value) {
strs.push_back(str);
}
}
}
// Main function to test the code
int main() {
std::vector<std::string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
groupAnagrams(strs);
for (const auto&str : strs) {
std::cout<< str << " ";
}
return 0;
}
Output
bat tan nat eat tea ate
In this scenario, the initial step involves establishing an unordered map called hashTable. Within this data structure, the keys consist of organized strings while the corresponding values represent collections of strings that function as anagrams. Subsequently, each string within the input vector strs is sequentially processed by sorting it to generate a key, which is then incorporated into the hash table. Concluding this process, the contents of the input vector "strs" are reset, paving the way for a traversal of the hash table to merge the various anagram clusters into strs.
There are alternative methods for categorizing anagrams within a sequence of strings in C++. One alternative involves employing a vector containing pairs to hold the sorted string as the initial element of each pair and the unaltered string as the subsequent element. Subsequently, the vector of pairs can be sorted according to the sorted string, positioning anagrams next to each other. Ultimately, the original strings can be extracted and retained in a distinct vector.
Example 2:
Here is an implementation of this approach:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
// Function to group anagrams
void groupAnagrams(std::vector<std::string>& strs) {
std::vector<std::pair<std::string, std::string>>sortedStrs;
for (const auto&str : strs) {
std::string sortedStr = str;
std::sort(sortedStr.begin(), sortedStr.end());
sortedStrs.push_back(std::make_pair(sortedStr, str));
}
std::sort(sortedStrs.begin(), sortedStrs.end());
strs.clear();
for (const auto&pair :sortedStrs) {
strs.push_back(pair.second);
}
}
// Main function to test the code
int main() {
std::vector<std::string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
groupAnagrams(strs);
for (const auto&str : strs) {
std::cout<< str << " ";
}
return 0;
}
Output
bat ate eat tea nat tan
In this particular approach, an initial step involves the creation of a vector named sortedStrs consisting of pairs. Each pair includes the sorted version of a string as the first element and the original string as the second element. Subsequently, a process is implemented where each string in the input vector strs is traversed, sorted to generate the sorted string, and then paired with the original string in sortedStrs. The sorting of sortedStrs is carried out by utilizing std::sort, which arranges the pairs in lexicographical order based on their sorted strings. Ultimately, the input vector "strs" is emptied, following which a loop is executed on sortedStrs to retrieve the second element of each pair and concatenate it to "strs".
This method operates with a time complexity of O(N M log M), where N represents the quantity of strings in the input array and M signifies the longest string's size. The spatial complexity amounts to O(N * M) due to the necessity of preserving the arranged strings for every input string.
Example 3:
An alternative method to achieve this is by utilizing the counting sort technique:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <unordered_map>
// Function to group anagrams
void groupAnagrams(std::vector<std::string>& strs) {
std::unordered_map<std::string, std::vector<std::string>> map;
for (const auto&str : strs) {
int count[26] = {0};
for (const auto&c : str) {
count[c - 'a']++;
}
std::string key;
for (int i = 0; i< 26; i++) {
key += std::to_string(count[i]) + "#";
}
map[key].push_back(str);
}
strs.clear();
for (const auto&pair : map) {
for (const auto& str : pair.second) {
strs.push_back(str);
}
}
}
// Main function to test the code
int main() {
std::vector<std::string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
groupAnagrams(strs);
for (const auto& str : strs) {
std::cout<< str << " ";
}
return 0;
}
Output
bat tan nat eat tea ate
In this particular implementation, we begin by establishing an unordered map named map. Within this map, the key is formed by arranging the characters in the string in a sorted manner based on their frequencies, while the corresponding value consists of a collection of the original strings that share the same sorted character arrangement. Subsequently, we proceed to cycle through each individual string in the input vector strs. During this process, we calculate the occurrence of each character by utilizing a counting array named count. The key is then generated by merging the count of each character together with a "#" separator. The original string is then added to the value vector associated with the key in the map. As a concluding step, we empty the input vector strs and navigate through the map to retrieve the value vectors and concatenate their elements to strs.
There are various alternative methods available, including:
- Hash Map approach: By utilizing a hash map data structure, we can group anagrams together based on their sorted strings. Each string can be sorted and used as a key in the hash map, with the original string stored as a value corresponding to its sorted version. Subsequently, we can iterate through the hash map to gather the anagram groups. This technique operates with a time complexity of O(N M log M), where N represents the quantity of strings in the input vector, and M signifies the longest string's length.
- Radix sort approach: Employing a radix sort algorithm allows us to categorize anagrams according to their sorted strings. By establishing an array of vectors, where each vector's index aligns with the sorted string, we can append the initial string to the corresponding vector. Following this, we can merge the vectors within the array to identify the anagram groups. This strategy showcases a time complexity of O(N * M), with N denoting the number of strings in the input vector and M representing the length of the longest string.
Each of these methods comes with its own set of pros and cons, and the most suitable method varies based on factors such as the size of the input array, the string lengths, and the memory capacity at hand.
