Group Anagrams

10.2 Group Anagrams: Write a method to sort an array of strings so that all the anagrams are next to each other.

• O(NlogN) time?, O(N) extra space

• One way of doing this is first sort the strings, and pair them into a map.

• Then we can sort the map by its second value, then return its first value.

typedef std::pair<std::string, string> p;
struct Comp {
    bool operator()(const p &left, const p &right) const {
        return left.first < right.second;
    }
};

void group_anagrams(vector<string> &strings) {
    map<string, string> word_anagram;

    for (int i = 0; i < strings.size(); i++) {
        string cpy = strings.at(i);
        sort(strings.at(i).begin(), strings.at(i).end());
        word_anagram.insert( { { cpy }, { strings.at(i) } });
    }

    // dump into vector in order to make it sortable
    vector<pair<string, string>> cpy(word_anagram.begin(), word_anagram.end());

    sort(cpy.begin(), cpy.end(), Comp());

    int count = 0;
    for (auto &i : cpy) {
        strings.at(count++) = i.first;
    }

}


int main() {
    vector<string> words = {"could", "cloud", "dance", "caned", "own", "now", "clams", "calms", "wings", "swing", "a" };

    group_anagrams(words);
    print(words);
}