[LeetCode][C++/Python] 49번: Group Anagrams (259)

 

생각의 흐름

문자열의 원소순으로 정렬을 하면 같은 anagram의 원소들은 같은 문자열을 갖게 된다. 이점을 이용하자.

 

예를 들어 다음과 같은 3개의 예시의 경우

"ate","eat","tea"

문자순으로 정렬하면 모두 "aet" 값을 갖게 된다. 이를 Map 자료형을 이용하여 처리하면 된다.

 

나의 코드

1. C++

using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> word_map;

        for (auto word : strs) {
            string temp = word;
            sort(temp.begin(), temp.end());
            word_map[temp].push_back(word);
        }

        vector<vector<string>> res;
        for(auto it : word_map) {
            res.push_back(it.second);
        }
        return res;
    }
};

 

2. Python

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        word_map = defaultdict(list)

        for s in strs:
            word_map["".join(sorted(s))].append(s)

        return list(word_map.values())