[LeetCode] 049 Group Anagrams

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

Group Anagrams - LeetCode

 

1. 첫 시도

Set 사용방법을 기억할만해서 틀린풀이지만 기록해본다. Set 안에 Set을 하나 더 넣어서 시도했다.

// input => vector<string>& str;

set<set<char>> bigSet;
for(string &s:strs)
{
    set<char> smallSet;

   /* Set은 중복을 허용하지 않고, Set 값이 저장될 때 순서가 정렬
      되므로 (a,b) (b,a) 같이 내부 값의 종류가 같으면 insert 실패 */
    for(char c:s)
    { 
        smallSet.insert(c); 
    }
	
    /* insert이후 pair<저장된 위치의 iterator, bool 삽입성공여부>
       값을 반환한다.*/
    auto InsertInfo = bigSet.insert(smallSet);
    bool isInserted = InsertInfo.second;
    if(!isInserted)
    { int index = distance(bigSet.begin(),InsertInfo.first); }
}

이 방법은 { a, a, a, b } 와 { a, a, b, b }를 동일하게 취급한다. 중복되는 문자의 개수는 무시되기 때문에 다른 방법을 사용해야한다.

 

2. 풀이

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> sort_map;
        
        for(auto &s:strs)
        {
            string temp = s;
            
            // 정렬이 되어야 다른 순서 같은 값을 분류할 수 있다.
            sort(temp.begin(), temp.end());
            
            // map[index]에서 index가 비어있으면 새로 만든다.
            sort_map[temp].push_back(s);
        }
        
        vector<vector<string>> result;
        for(auto &a:sort_map)
        {
            result.push_back(a.second);
        }
        return result;
        
    }
};

 

 

참고

https://leetcode.com/problems/group-anagrams/discuss/19200/C%2B%2B-unordered_map-and-counting-sort

https://leetcode.com/problems/group-anagrams/discuss/1398888/C%2B%2BPython-Group-by-sorted-string-group-by-count-characters-Solutions-Clean-and-Concise