MEDIUM

Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example

Input:

strs = ["eat","tea","tan","ate","nat","bat"]

Output:

[["eat","tea","ate"],["tan","nat"],["bat"]]

Explanation:
Words with the same letters are grouped together.

Constraints

1 ≤ strs.length ≤ 10⁴
0 ≤ strs[i].length ≤ 100
strs[i] consists of lowercase English letters.

Solution: Hash Table

Time Complexity: O(N * K log K), where N is the length of strs and K is the maximum length of a string.
Space Complexity: O(N * K)

C++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (auto& s : strs) {
            string t = s;
            sort(t.begin(), t.end());
            mp[t].push_back(s);
        }
        vector<vector<string>> res;
        for (auto& p : mp) res.push_back(p.second);
        return res;
    }
};