49_group_anagrams__UNOPTIMZED.cc

#include <unordered_map>
 
class Solution {
public:
    std::unordered_map<char, int> computeMap(const std::string& s) {
        std::unordered_map<char, int> m;
 
        for (const char& c: s) {
            if (!m.contains(c)) m[c] = 0;
            m[c]++;
        }
 
        return m;
    }
 
    bool isAnagram(const std::string& s, const std::unordered_map<char, int>& m) {
        std::unordered_map<char, int> smap;
        for (const char& x: s) {
            if (!m.contains(x)) return false;
            if (!smap.contains(x)) smap[x] = 0;
            smap[x]++;
        }
        return (smap == m);
    }
 
    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;
        }
 
        std::vector<std::unordered_map<char, int>> partition_maps;
        
        for (const std::string& s: strs) {
            bool was_adjusted = false;
 
            for (int i = 0; i < sol.size(); i++) {
                // check if s is anagram with partition_maps[i]
                if (s.length() != sol[i][0].length()) continue;
                if (!isAnagram(s, partition_maps[i])) continue;
                sol[i].push_back(s);
                was_adjusted = true;
                break;
            }
 
            if (was_adjusted) continue;
            // create new partion & corresponding map
            sol.push_back(std::vector<std::string>{ s });
            partition_maps.push_back(computeMap(s));
        }
 
        return sol;
    }
};