[leetcode 49] 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 1:

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

Example 2:

Input: strs = [""] Output: [[""]]

Example 3:

Input: strs = ["a"] Output: [["a"]]

 

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lower-case English letters.

문제 풀이:

-매핑을 사용하는 문제이다. 매번 포문을 돌리면 TLE가 난다.

- map의 사용: 맵에 value값으로 벡터도 넣을 수 있다!

매 string마다 정렬을 해서 일치하는 키값에 value로 넣는다.

class Solution {
public:
    
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        int n = strs.size();
        if(n==0){
            return result;
        }
        unordered_map<string, vector<string>> um;
        for(int i=0; i<n; i++){
            string cmp = strs[i];
            sort(cmp.begin(), cmp.end());
            um[cmp].push_back(strs[i]);
        }
        
        for(auto it = um.begin(); it!=um.end(); it++){
            result.push_back(it -> second);
        }
        return result;
    }
};