[Leetcode] 49. Group Anagrams

Identifying the Problem

strs 에서 anagram 인 단어들을 묶어 리턴한다.

 

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

Organizing thoughts

지난 번 anagram의 lettermap을 참고하면 쉽게 풀 수 있을 거라 생각했다.

[Leetcode] 242. Valid Anagram

1. strs의 모든 단어의 lettermap을 추출

2. strs size 만큼 반복하며 동일한 lettermap일 경우 단어를 묶는다.

3. 단, 탐색하는 단어와 비교하는 단어가 같은 경우,

   비교하는 단어는 중복을 방지하기 위해 해당 단어의 index를 flag를 세워 탐색을 건너뛴다. 

 

 

Sourcecode

## 직접 작성한 코드 

짧은 example에서는 제대로 작동하지만, Time Limit Exceeded 발생

시간복잡도가 O(n)가 되어야한다. 

#include <algorithm>

template <class T>
static bool compareVectors(std::vector<T> a, std::vector<T> b)
{
   if (a.size() != b.size())
   {
      return false;
   }
   ::std::sort(a.begin(), a.end());
   ::std::sort(b.begin(), b.end());
   return (a == b);
}

class Solution {
public:
    
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {

    vector<vector<string>> ans;
    vector < vector <int> > lettermap(strs.size(),vector <int>(26,0));

    vector<int> flag(strs.size() , 0);
    
    int ans_c = 0; //동일 단어의 그룹 index
        
    for(int i = 0; i<strs.size(); i++) //lettermap 을 작성
        for(int k = 0; k<strs[i].size(); k++)
            lettermap[i][strs[i][k] - 'a'] +=1;
        
    for(int i = 0; i<strs.size(); i++) //탐색단어과 비교단어가 같은 지
    {
        if(flag[i] == 0)
        {
            ans.push_back(vector<string> ()); //ans 벡터의 행을 하나 추가한다.
            
            if(i == strs.size() - 1) 
            //마지막 단어의 경우 중복되었는지 아닌지만 판단하면 된다.
            //중복이 아닌 경우 단일 그룹에 추가
                ans[ans_c].push_back(strs[i]);
            
            else
            {   
                ans[ans_c].push_back(strs[i]); //탐색 단어를 그룹의 처음에 넣고 시작
                for(int k = i+1; k<strs.size(); k++)
                    if(lettermap[i] == lettermap[k]) //두 lettermap 벡터가 같다면,
                    {
                        ans[ans_c].push_back(strs[k]); //동일 단어그룹에 추가한다.
                        flag[k] = 1; //중복 방지 flag
                    }
            }
          
          ans_c +=1; //그룹 변경
        }
    }
    
    return ans; 
    }
    
    
};

##정답 코드 및 출처

정답 코드는 lettermap간의 비교가 아닌, 단어를 오름차순 정렬한 상태를 map에 집어 넣었다.

아직 hashmap과 map에 대해 잘 모르는 상태라 더 공부해보아야겠다.

C++ unordered_map and counting sort - LeetCode Discuss

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        
        for (string s : strs) {
            string t = s;
            sort(t.begin(), t.end());
            mp[t].push_back(s);
        }
        vector<vector<string>> anagrams;
        for (auto p : mp) { 
            anagrams.push_back(p.second);
        }
        return anagrams;
    }
};

 

 

Mistake

2차원 벡터를 선언하고, ans.push_back(vector<string> ()); 로 하나의 행을 만들어줘야 값을 집어 넣을 수 있다.

New things learned

• 2차원 벡터 선언 방식

[C++] 2차원벡터 사용 예시