LeetCode/Group Anagrams

"apple" 이 3개가 있으면 그대로 3개를 넣어야 한다는 점에 유의해야 한다.

"eat" "ate" "tea"를 어떻게 하나로 묶을까를 우선 생각해 봐야 한다. 하나의 그룹에 대해서 묶을 방법만 생각해낸다면 다른 그룹에 대해서도 묶을 수 있고 이것들을 그대로 vector에 담아서 return하면 되기 때문.

처음에는 eat의 알파벳별 개수를 map에 저장해서 strs를 순회하며 같으면 set에 넣고 하는 방식으로 하려고 했었다. 하지만 잘 생각해보면 문제에 이미 힌트가 있다. -> '이루는 알파벳의 종류와 수가 같다'

즉, 정렬하면 같은 단어가 된다는 말이다. 이를 이용해서 정렬한 단어를 key로 이용하고 원래 단어를 value로 쓴다.

map을 하나 만들어서 key를 string, value를 vector<string>으로 설정한 뒤 사용하면 된다.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        unordered_map<string, vector<string>> m;
        string s;
        
        int n = strs.size();
        for(int i=0; i < n; ++i)
        {
            s = strs[i];
            sort(s.begin(), s.end());
            m[s].push_back(strs[i]);
        }
        
        for(auto e : m)
        {
            ret.push_back(e.second);
        }
        
        return ret;
    }
};