[C++] Group Anagrams

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

Group Anagrams - LeetCode

 

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

 

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

• There is no string in strs that can be rearranged to form "bat".
• The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
• The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

 

이전에 풀었던 Valid Anagram의 좀더 복잡한 버젼이다.

 

우선 생각나는 방식은 브루트 포스로 하나를 기준으로 순회하면서 일치하는 string은 하나의 벡터로 몰아넣고 erase하면 되지 않을까 했는데

 

class Solution {
public:
    bool isAna(string a, string b){
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        return a == b;
    }
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> answer;
        for(auto it = strs.begin();it != strs.end();it++){
            vector<string>group;
            for(auto iter = it + 1;iter != strs.end();){
                if(isAna(*it, *iter)){
                    group.push_back(*iter);
                    iter = strs.erase(iter);
                }else{
                    iter++;
                }
            }
            group.push_back(*it);
            answer.push_back(group);
        }
        return answer;
    }
};

시간 초과떠서 뇌정지오긴 했다.

erase 쓰는게 좀 오바같긴 하다.같은거 있어도 O( n^2 )이고 다 달라도 O( n^2 )이니깐 

이후에 계속 째려보다가 30분째 유혹을 못이기고 지피티한테 물어봤다.

지피티는 그냥 해시맵을 써서 풀었다.

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

    for (auto &s : strs) {
        string key = s;
        sort(key.begin(), key.end());

        mp[key].push_back(s);
    }
   for (auto &[k, v] : mp){
    answer.push_back(move(v));
    }
    return answer;
}
};

key를 정렬한 string으로 넣고 일치하면 넣고 아니면 새로 생성하면 되니깐.

 

리트코드는 보면 해시맵을 써서 푸는 문제가 많은거 같다. 애매하다~ 싶으면 해시맵부터 때려넣어보자.

 

여튼 보니깐 참 쉽다. 뇌가 꽤 맨들맨들한것 같지만 계속 풀어보자