« Group anagrams

Using hashmap

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14void grouper(vector<string> mylist)
15{
16    map<map<char, int>, vector<string> > myMap;
17
18    for (int i = 0; i < mylist.size(); i++)
19    {
20        string curr = mylist[i];
21        map<char, int> frequencyMap;
22        for (int j = 0; j < curr.length(); j++)
23        {
24            map<char, int>::iterator it = frequencyMap.find(curr[j]);
25            if (it != frequencyMap.end())
26            {
27                frequencyMap[curr[j]]++;
28            }
29            else
30            {
31                frequencyMap[curr[j]] = 1;
32            }
33        }
34
35        map<map<char, int>, vector<string> >::iterator im = myMap.find(frequencyMap);
36        if (im != myMap.end())
37        {
38            vector<string> temp_my_list;
39            temp_my_list.push_back(curr);
40            myMap[frequencyMap].push_back(curr);
41        }
42        else
43        {
44            myMap[frequencyMap].push_back(curr);
45        }
46    }
47
48    vector<vector<string> > result;
49
50    for (auto it = myMap.begin();
51         it != myMap.end(); ++it)
52    {
53        result.push_back(it->second);
54    }
55
56    for (int i = 0; i < result.size(); ++i)
57    {
58        cout << "[";
59        for (int j = 0; j < result[i].size(); ++j)
60        {
61            cout << result[i][j] << ", ";
62        }
63        cout << "]";
64    }
65}
66
67int main()
68{
69    vector<string> mylist;
70    mylist.push_back("cat");
71    mylist.push_back("dog");
72    mylist.push_back("ogd");
73    mylist.push_back("god");
74    mylist.push_back("atc");
75    mylist.push_back("cat");
76    grouper(mylist);
77    return 0;
78}

Time Complexity :

O(M+N)

Sorting Each String

Copy
1#include<iostream>
2#include<iomanip>
3#include<algorithm>
4#include<string>
5#include<cstring>
6#include<vector>
7#include<cmath>
8#include <map>
9#include<climits>
10//climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14void grouper(vector<string> mylist){
15    unordered_map<string, vector<string> > myMap;
16
17    for(int i=0; i<mylist.size(); i++){
18        string curr = mylist[i];
19        string str = curr;
20        sort(str.begin(), str.end());
21
22        unordered_map<string, vector<string> >::iterator it = myMap.find(str);
23
24        if(it != myMap.end()){
25            myMap[str].push_back(curr);
26        }else{
27            vector<string> vec;
28            vec.push_back(curr);
29            myMap[str]=vec;
30        }
31    }
32
33    vector<vector<string> > result;
34
35    unordered_map<string, vector<string> >::iterator it;
36    for (it = myMap.begin(); it != myMap.end(); it++) {
37        vector<string> values = myMap[it->first];
38        result.push_back(values);
39    }
40
41    for (int i = 0; i < result.size(); ++i)
42    {
43        cout << "[";
44        for (int j = 0; j < result[i].size(); ++j)
45        {
46            cout << result[i][j] << ", ";
47        }
48        cout << "]";
49    }
50}
51int main()
52{
53    vector<string> mylist;
54    mylist.push_back("cat");
55    mylist.push_back("dog");
56    mylist.push_back("ogd");
57    mylist.push_back("god");
58    mylist.push_back("atc");
59    mylist.push_back("cat");
60    grouper(mylist);
61    return 0;
62}

Time complexity:

Let there be N-words and each word has a maximum of M characters.

O(NMLogM ).