Tuesday, April 30, 2024 23:29 EDT

Leetcode 49. Group Anagrams (Medium)

I decided to pickup another quick one. Interesting how some of the easy ones I find to be much more difficult than mediums.

Approach
The task is to group anagrams together and return them as a vector<vector<string>>.

In my first approach I tried to create an unordered_map<unordered_map<char, int>, vector<string>>. Don't laugh. My logic was by creating an unordered_map of how many times each char appears in each string, I can say m[stringMap].push_back(str). While this didn't work it did help me on the right track.

Let me break down my thought process for the final solution.

m is an unordered_map that has the following:

• key = the sorted (a-z) string
• value = a vector of all the original strings in their unsorted stated

Now, I loop through the strings.

I store the original string in a temporary string variable t. This is because the next line is going to sort the string in-place a-z. This acts as a key. So for example, if tan is one string and ant is another, after sorting they will both be ant. Lastly, inside the loop, I add a new key-value entry (if it doesn't already exist) and push_back into the vector the original string stored in t.

Now there is nothing more to do than loop over the map keys and push the entirety of the vector (it->second) into the two-demensional result vector r.

Complexity
Time Complexity: O(n log n)
Space Complexity: O(n)

Code

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for(string s : strs){
            string t = s;
            sort(s.begin(), s.end());
            m[s].push_back(t);
        }
        vector<vector<string>> r;
        for(auto it = m.begin(); it != m.end(); it++){
            r.push_back(it->second);
        }
        return r;
    }
};