~/leetcode $ 49. Group-Anagrams

Very similar problem to the valid anagram question that was done two days ago.

Here, we want to group each string into valid anagrams of each other. Intuitively, we can think about keeping track of ‘anagram groups’ where every element in each group is a valid anagram of each other, which can be done with a hashmap.

The problem then would be what do we use as the key or identifier for each of these groups? A few options for the key are:

1. sorted string
   • for example, let’s say you had “eat”, “ate”, “tea”. If you sort the characters alphabetically for each word, you would get “aet” for all 3 strings (and thus, these words would be grouped under the key “aet” - i.e. { "aet": ["eat", "ate", "tea"] }
   • this also consider letters that appear more than once (for example, hello -> ehllo)
2. hashmap of counts
   • using the example above, { {'a': 1, 'e': 1, 't': 1}: ["eat", "ate", "tea"] }
   • this one is kind of ugly - using maps as keys feel kind of wrong
3. array
   • each index corresponds to the letter (26 spots for 26 lowercase english letters) e.g. index 0 is for ‘a’, 1 is for ‘b’, etc…
   • each value in the array corresponds to the count (and thus, initially all zero)
   • we can get the index by using the ascii value of each letter and subtracting the ascii value of ‘a’

I feel like either option 1 or 3 is very nice… The overhead in option 1 would be sorting each character and then string comparison while the overhead in option 3 would be the memory of the array and array comparison…

I think option 1 is slightly nicer and easier to write so I’ll go with that… so again, we need to learn a bit more cpp :D

• std::sort(word.begin(), word.end()) sorts the word in place (in the <algorithm> header)
• when we iterate over the hashmap using a for loop, we get back pair<keyType, valueType> object

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> anagramGroups {};
        for (string word: strs) {
            string sortedWord = word;
            sort(sortedWord.begin(), sortedWord.end());
            if (anagramGroups.contains(sortedWord)) {
                anagramGroups[sortedWord].push_back(word);
            } else {
                anagramGroups[sortedWord] = {word};
            }
        } 

        vector<vector<string>> result {};
        for (const pair<string, vector<string>>& element: anagramGroups) {
            result.push_back(element.second);
        }

        return result;
    }
};

Time Complexity: O(m * n log n) - m is the number of words in the list, n is the max length of the string

Space Complexity: O(mn)

Time Taken: 7m 36s