This content originally appeared on DEV Community and was authored by Phoenix
Problem Link - Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
For example:
inputStr = {"eat","tea","tan","ate","nat","bat"}
Here {“tea”, “ate”,” eat”} and {“nat”, “tan”} are grouped as anagrams. Since there is no such string in “inputStr” which can be an anagram of “bat”, thus, “bat” will be the only member in its group.
Intuition && Approach
- Anagrams are words or phrases that are formed by rearranging the letters of another, using all the original letters exactly once.
- To identify anagrams, if the count of number of characters in 2 words are same, then it is an anagram. this means if we sort the 2 words then we get the same result.
- So we declare a hashmap that stores the key-value pairs, where key is the sorted version of the word and values are the list of all words that matches this key whose sorted version is same.
- So we iterate through the list of words, for each we will find the sorted version of that word, and find the key in map and update its value list by adding this word.
Code
#include <bits/stdc++.h>
using namespace std;
vector<vector<string>> getGroupedAnagrams(vector<string> &input,int n) {
// Using an unordered map to group anagrams
unordered_map<string, vector<string>> mp;
for (const string& str : input) {
string temp = str; // Copy the original string
sort(temp.begin(), temp.end()); // Sort the string to find the key
mp[temp].push_back(str); // Group anagrams together
}
// Prepare the result from the map
vector<vector<string>> ans;
for (const auto& it : mp) {
ans.push_back(it.second);
}
return ans;
}
Time Complexity: O(n * m(log m)), where m is the length of a word.
A single traversal through the array is needed.
Space Complexity: O(n).
There are n words in a string. The map requires O(n) space to store the strings.
This content originally appeared on DEV Community and was authored by Phoenix
Phoenix | Sciencx (2024-09-25T18:52:28+00:00) Group Anagrams. Retrieved from https://www.scien.cx/2024/09/25/group-anagrams/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.