49. Group Anagrams

📝 Problem Details

• Title: 49. Group Anagrams
• Link: https://leetcode.com/problems/group-anagrams/
• Difficulty: Medium
• Tags/Categories: Arrays Hashmap

💡 Explanation of Solution

- use a hashmap where the key value pair is:
	- key: the sorted version of the string
	- value: a vector of all anagrams that can be made from that sorted string

- if the sorted string already exists in the hashmap, push the current string into its vector
- if it doesnt exist, create a new record in the hashmap

- after all strings have been populated in the map, push all results into a results vector (2D vector)
- return the results vector

⌛ Complexity Analysis

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

💻 Implementation of Solution

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
 
        // sort the string, make it the key and insert every element related to that sorted key
        for(int i=0; i < strs.size(); i++) {
            string sortedString = strs[i];
            sort(sortedString.begin(), sortedString.end());
 
            if(groups.find(sortedString) != groups.end()) {
                groups[sortedString].push_back(strs[i]);
            } else {
                groups[sortedString] = {strs[i]};
            }
        }
 
        vector<vector<string>> result;
        for(auto& it : groups) {
            result.push_back(it.second);
        }
 
        return result;
    }
};