49_group_anagrams.cc

#include <vector>
#include <string>
#include <unordered_map>
#include <cstddef>
#include <utility>
 
// this is for std::unordered_map, it does: std::array<int, 26) --> some hash i.e. std::size_t
struct array26Hasher {
    std::size_t operator()(const std::array<int, 26>& arr) const noexcept {
        std::size_t h = 0;
        for (int i : arr) {
            h += h * 31 + i;
        }
        return h;
    }
};
 
class Solution {
public:
    std::array<int, 26> computeKey(const std::string& s) {
        std::array<int, 26> key = {0};
        int anchor = (int)'a';
 
        for (const char& c : s) key[(int)c - anchor]++;
        return key;
    }
 
    std::vector<std::vector<std::string>> groupAnagrams(
        std::vector<std::string>& strs
    ) {
        std::vector<std::vector<std::string>> sol;
 
        if (strs.size() == 1) {
            sol.push_back(std::vector<std::string>{ strs[0] });
            return sol;
        }
 
        sol.reserve(strs.size());
        
        /*
 
        we basicaly make 
        [1,0,0, ...] = {"eat", "tea", ...}
        [1,1,0, ...] = {"bat", ...}
        ...
 
        so it is important to reserve the space as each {} vector increases in size,
        this will cause us to copy a lot of data in the end when compiliing the final
        vec vec str (vvs), so we don't want this vvs reallocate each time we push vs to it.
 
        we reserve the partitions because each time a new key is added, the map will
        rehash all of the keys
        */
 
        std::unordered_map<
            std::array<int, 26>, std::vector<std::string>, array26Hasher
        > partitions;
        partitions.reserve(strs.size());
        
        for (const std::string& s: strs) {
            partitions[computeKey(s)].push_back(s);
        }
 
        // instead of copying, move the results
        for (auto&[_, group] : partitions) {
            sol.push_back(std::move(group));
        }
 
        return sol;
    }
};