In: Computer Science
Write a program (O(n), where n is the number of words) that takes as input a set of words and returns groups of anagrams for those words. Complete your code here Do not change anything in the test file.
CPP File:
#include
#include
#include
#include
using namespace std;
vector> findAnagrams(const vector& dict);
vector> findAnagrams(const vector& dict)
{
// Your code here...
}
Test File:
#include
#include
#include
#include
using namespace std;
vector> findAnagrams(const vector& dict);
int main()
{
vector word_list = {"debitcard", "elvis", "silent", "badcredit",
"lives", "freedom", "listen", "levis"};
vector> result = findAnagrams(word_list);
for (auto anagrams: result) {
for (auto words: anagrams)
cout << words << " ";
cout << endl;
}
return 0;
/* Output should be -
silent listen
debitcard badcredit
elvis lives levis
*/
}
The expected output should be in this order ONLY:
freedom
silent listen
debitcard badcredit
elvis lives levis
code snippet for the function findAnagrams:
{
// Your code here...
vector<string>original, new_list;
new_list.insert(new_list.end(), dict.begin(), dict.end());
for (string &s : new_list)
sort(s.begin(), s.end());
unordered_map<string, vector<int>> map;
for (int i = 0; i < dict.size(); i++)
map[new_list[i]].push_back(i);
vector<vector<string>> ans;
for (auto itr : map)
{
vector<string>tmp;
for (int index : itr.second)
tmp.push_back(dict[index]);
ans.push_back(tmp);
}
return ans;
}
Complete code including driver main function to run in single file:
#include<bits/stdc++.h>
using namespace std;
vector<vector<string>> findAnagrams(const vector<string>&dict)
{
// Your code here...
vector<string>original, new_list;
new_list.insert(new_list.end(), dict.begin(), dict.end());
for (string &s : new_list)
sort(s.begin(), s.end());
unordered_map<string, vector<int>> map;
for (int i = 0; i < dict.size(); i++)
map[new_list[i]].push_back(i);
vector<vector<string>> ans;
for (auto itr : map)
{
vector<string>tmp;
for (int index : itr.second)
tmp.push_back(dict[index]);
ans.push_back(tmp);
}
return ans;
}
int main()
{
vector<string>word_list= {"debitcard", "elvis", "silent", "badcredit", "lives", "freedom", "listen", "levis"};
vector<vector<string>> result = findAnagrams(word_list);
for (auto anagrams : result) {
for (auto words : anagrams)
cout << words << " ";
cout << endl;
}
return 0;
}
EXPLANATION:
created another list and sorted each word to create a index for individual anagramic strings and after that created a map to store the index of all anagramic strings together (grouped). After that interated through the map and stored the same grouped anagramic strings together and returned the vector of vector strings.
NOTE: if any doubt or problem with the code let me know in the comment section and do upvote.