[ArraysHashing][Medium] 49. Group Anagrams

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

 

문장들의 배열이 주어질 때, anagram이 같은 것들끼리 묶어서 출력하라. 

 

우선 이 문제를 풀때는 frequency buff를 사용한다는 생각에 미치는 것이 일반적이다. 

하지만 조금 더 최적화를 위해서를 입력된 문자를 정렬하면 anagram이 같은 문자는 같은 문자로 정리된다는 생각에 까지 이르러야 한다. 

 

코드 

vector<vector<string>> groupAnagrams(vector<string>& strs) 
{
    map<string, vector<int>> mBuff;
    for (auto k = 0; k < strs.size(); ++k)
    {
        string cur = strs[k];
        sort(cur.begin(), cur.end());

        if (mBuff.find(cur) == mBuff.end())
            mBuff[cur] = vector<int>{ k };
        else
            mBuff[cur].push_back(k);
    }


    vector<vector<string>> vRet;
    for (auto iter = mBuff.begin(); iter != mBuff.end(); ++iter)
    {
        auto vIdx = iter->second;
        vector<string> vStr;
        for (auto j = 0; j < vIdx.size(); ++j)
            vStr.push_back(strs[vIdx[j]]);

        vRet.push_back(vStr);
    }
    return vRet;
}

 

 

결과