49 Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

  • Algorithm:

    • Map each sorted word (key) to its actual word (vector of values).

    • Thats it

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> map;

    for (auto str : strs) {
        string word = str;
        sort(str.begin(), str.end());

        //auto &found = map.find(str);
        if (map.find(str) == map.end()) {
            map.insert({ { str },{ word } });
        }
        else {
            map.find(str)->second.push_back(word);
        }
    }

    vector<vector<string>> anagrams;
    for (auto i : map) {
        anagrams.push_back(i.second);
    }

    return anagrams;
}

int main() {
    vector<string> strs = {
        "eat", "tea", "tan", "ate", "nat", "bat"
    };

    print2d(groupAnagrams(strs));

}

Last updated