Question

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 -

For example, if the list is "debitcard", "elvis", "silent", "badcredit", "lives", "freedom", "listen", "levis",

the output should be

silent listen
debitcard badcredit
elvis lives levis

Note that freedom has no anagram, and hence is not printed.

///////////////////////////////////////////////$%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

anagram.cpp

#include <iostream>

#include <unordered_map>

#include <vector>

#include <algorithm>

using namespace std;

vector<vector<string>> findAnagrams(const vector<string>& dict);

vector<vector<string>> findAnagrams(const vector<string>& dict)

{

// Your code here...

}

////////////////////////////////////////$%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

anagram_test.cpp

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;
vector<vector<string>> findAnagrams(const vector<string>& dict);

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;
  
/* Output should be -
  
silent listen
debitcard badcredit
elvis lives levis
  
*/
}

Words that are anagrams are identical when sorted by characters. Use this as the key to a hashtable (unordered_map STL) with key as string, and value as vector<string>

PLEASE KEEP THE TEST FILE SEPERATE.

Thank you for your help.

Answer 1

ALGORITHM

• Using Unordered map and Count sort we can solve it in O(M*N) Time complexity.
• There is no approach that can solve it in O(N) Time. Even Trie also Take O(M*NlogN) time.
• After applying count sort on each string fill it in map of string,vector<string> and then print it.

CODE

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

// Count Sort Takes O(n+k) time to Sort
// where n is the number of elements in input array and k is the range of input.

string Sort(string s) {
        int counter[26] = {0};
        for (char c : s) {
            counter[c - 'a']++;
        }
        string t;
        for (int c = 0; c < 26; c++) {
            t += string(counter[c], c + 'a');
        }
        return t;
}

// Finding the Anagrams using unordered map and sorting technique.
vector<vector<string>> findAnagrams(const vector<string>& dict)
{
        unordered_map<string, vector<string>> m;
        for (string s : dict) {
            m[Sort(s)].push_back(s);
        }
        vector<vector<string>> res;
        for (auto p : m) { 
                if(p.second.size()>1)
            res.push_back(p.second);
        }
        return res;

}

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;
  
/* Output should be -
  
silent listen
debitcard badcredit
elvis lives levis
  
*/
}

OUTPUT