[Hashing][Medium] 49. Group Anagrams

https://leetcode.com/problems/group-anagrams/description

 

Q. 문자열이 주어질 때, 이 문자들을 같은 anagram 단어들의 그룹으로 묶어서 출력하라. 

 anagram 은 각 캐릭터의 위치 변경으로 구성할 수 있는 다른 단어들을 의미한다. 

 따라서 각 캐릭터들은 모든 단어에 1회씩 등장한다. 

 

Solution. 

 각 string을 대표할 수 있는 하나의 key를 만들고 해당 key에 매칭되는 string끼리 묶으면 될 것이다. 

 단어들은 같은 캐릭터들의 조합들의 모음이므로, 정렬하면 같은 캐릭터 순서가 나올 것이다. 

 

 이를 이용해 map을 만들어 단어를 묶는다. 

 

 

 vector<vector<string>> groupAnagrams(vector<string>& strs) 
{
    unordered_map<string, vector<string>> group;
    for(int q = 0; q < strs.size(); ++q)
    {
        string cur = strs[q];
        sort(cur.begin(), cur.end());

        if(group.find(cur) != group.end())
            group[cur].push_back(strs[q]);
        else 
        {
            vector<string> vTemp(1, strs[q]);
            group[cur] = vTemp;
        }
    }

    vector<vector<string>> vOut;
    unordered_map<string, vector<string>>::iterator it = group.begin();
    for(; it != group.end(); ++it)
    {
        vOut.push_back(vector<string>(it->second));
    }
    return vOut;
}

 

적절한 결과를 얻었다. 

 

Note) 단어가 anagrams이 아니라면, 각 단어별로 character에 대한 frequency map을 만들어야 하는 등 훨씬 더 복잡하고, 지저분한 과정이 들어가야 할 것이다. 

따라서 문제의 핵심은 sort로 key를 통일시킬 수 있냐 하는 것이다.