Group Anagrams Solutions in C++

// Source : https://oj.leetcode.com/problems/anagrams/
// Author : Hao Chen
// Date   : 2014-07-18



class Solution {
public:
    vector< vector<string> > groupAnagrams(vector<string> &strs) {
        vector< vector<string> > result;
        map<string, int> m;
        for(int i=0; i<strs.size(); i++){
            string word = strs[i];
            sort(word.begin(), word.end());
            if (m.find(word)==m.end()){
                vector<string> v;
                v.push_back(strs[i]);
                result.push_back(v);
                m[word] = result.size()-1;
                
            }else{
                result[m[word]].push_back(strs[i]);
            }
        }
        
        for(int i=0; i<result.size(); i++){
            sort(result[i].begin(), result[i].end());
        }
        return result;
    }
     
    //using multiset 
    vector< vector<string> > groupAnagrams01(vector<string> &strs) {
        vector< vector<string> > result;
        map<string, multiset<string>> m;
        for(int i=0; i<strs.size(); i++){
            string word = strs[i];
            sort(word.begin(), word.end());
            m[word].insert(strs[i]);
        }
        
        for(auto item : m){
            vector<string> v(item.second.begin(), item.second.end());
            result.push_back(v);
        }
        return result;
    }


    //NOTICE: the below solution has been depracated as the problem has been updated!
    vector<string> anagrams(vector<string> &strs) {
        vector<string> result;
        map<string, int> m;
        for(int i=0; i<strs.size(); i++){
            string word = strs[i];
            //sort it can easy to check they are anagrams or not
            sort(word.begin(), word.end());  
            if (m.find(word)==m.end()){
                m[word] = i;
            }else{
                if (m[word]>=0){
                    result.push_back(strs[m[word]]);
                    m[word]=-1;
                }
                result.push_back(strs[i]);
            }
        }
        return result;
    }
};

#include <string>
using std::string;
#include <vector>
using std::vector;
#include <unordered_map>
using std::unordered_map;
#include <algorithm>
using std::sort;

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        unordered_map<string, vector<string>::iterator> cache;
        vector<string> ret;
        for (auto iter = strs.begin(); iter != strs.end(); ++iter) {
            string tmp_str(*iter);
            sort(tmp_str.begin(), tmp_str.end());
            auto found = cache.find(tmp_str);
            if (found == cache.end())
                cache[tmp_str] = iter;
            else {
                ret.push_back(*iter);
                if (found->second != strs.end()) {
                    ret.push_back(*found->second);
                    found->second = strs.end();
                }
            }
        }
        return ret;
    }
};

/// Source : https://leetcode.com/problems/group-anagrams/description/
/// Author : liuyubobobo
/// Time   : 2018-09-12

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

using namespace std;


/// Using HashMap
/// Using sorted string as key
///
/// Time Complexity: O(n*klogk) where k is the max length of string in strs
/// Space Complexity: O(n*k)
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        unordered_map<string, vector<string>> map;
        for(const string& s: strs){
            string key = s;
            sort(key.begin(), key.end());
            map[key].push_back(s);
        }

        vector<vector<string>> res;
        for(const auto& p: map)
            res.push_back(p.second);
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/group-anagrams/description/
/// Author : liuyubobobo
/// Time   : 2018-09-12

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

using namespace std;


/// Using HashMap
/// Using characters frequency as key
///
/// Time Complexity: O(n*k) where k is the max length of string in strs
/// Space Complexity: O(n*k)
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        unordered_map<string, vector<string>> map;
        for(const string& s: strs){
            string key = getKey(s);
            map[key].push_back(s);
        }

        vector<vector<string>> res;
        for(const auto& p: map)
            res.push_back(p.second);
        return res;
    }

private:
    string getKey(const string& s){
        vector<int> freq(26, 0);
        for(char c: s)
            freq[c - 'a'] ++;
        string key = "";
        for(int num: freq)
            key += to_string(num) + "#";
        return key;
    }
};


int main() {

    return 0;
}