[LeetCode] C++ 49. Group Anagrams

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

 

문제

 

문제 분석

- 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것이 anagram. 즉, 여기서는 anagram 관계를 가지는 것들을 모아서 반환하라는 것입니다.

- anagram 관계에 있는 문자열들을 정렬하면 같은 문자열이 나올 것이기 때문에 이를 활용하면 될 것이라고 생각했습니다.

(ex. ate -> aet, eat -> aet, tea -> aet)

- 정렬 후 나온 문자열에 대해서 빠른 접근이 가능하도록 hash를 사용한 unordered_map을 사용하는 것이 좋다고 생각했습니다. key를 정렬 후 나온 문자열, value로 string vector를 가지고 있고 value에 계속 추가하는 방식을 쓰기로 하였습니다.

 

풀이 1

class Solution {
private:
    string sortStr (string s){
        sort(s.begin(), s.end());
        return s;
    }
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        string sortedStr;
        vector<vector<string>> result;
        unordered_map<string, vector<string>> anagrams;
        for(const auto &s : strs){
            sortedStr = sortStr(s);
            anagrams[sortedStr].push_back(s);
        }

        for(const auto& pair : anagrams){
            result.push_back(pair.second);
        }
        return result;
    }
};