[알고리즘] LeetCode 49번 "Group Anagrams" (C/C++) - Don 임베디드

문제요약:

Given an array of strings strs, group the anagrams together and return the array of groups.

The order of the group does not matter.

An anagram is a word formed by rearranging the letters of a different word,

typically using all the original letters only once.

 

제약:

1 <= strs.length <= 10^4

0 <= strs[i].length <= 100

strs[i] consists of lowercase English letters only.

 

예제 1 입력.	예제 1 출력.
strs = ["eat","tea","tan","ate","nat","bat"]	[["bat"],["nat", "tan"],["ate","eat","tea"]]
예제 2 입력.	예제 2 출력.
strs = [""]	[[""]]
예제 3 입력.	예제 3 출력.
strs = ["a"]	[["a"]]

 

 

정답코드:

class Solution {
public:
    vector<string> keyStrings;
    unordered_map <string, vector<string>> myHashmap;
    
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        
        vector<vector<string>> vvResult;
        
        for(int i = 0; i < strs.size(); i++)    // O(N)
        {
            string sTmp = strs[i];
            string sSorted = sTmp;
            sort(sSorted.begin(), sSorted.end());    // sort the sTmp   // O(K(logK))
            
            // push the original string sTmp to hashmap
            if (myHashmap.find(sSorted) == myHashmap.end())
            {
                // add the sorted string to keyStrings
                keyStrings.push_back(sSorted);
                
                // create a new vector
                vector<string>* v = new vector<string>;
                v->push_back(sTmp);
                
                pair <string, vector<string>> p = make_pair(sSorted, *v);
                myHashmap.insert(p);
            }
            else
            {
                // push the sorted string 
                myHashmap.find(sSorted)->second.push_back(sTmp);
            }
        }
        
        for(int j = 0; j < keyStrings.size(); j++)  // O(N)
        {
            vector<string> subVector = myHashmap.find(keyStrings[j])->second;
            vvResult.push_back(subVector);
        }
        return vvResult;
    }
};

핵심 Idea:

Hash key로 정렬된 배열을 사용하기.

Time complexity : O(N* KlogK)

Space complexity: O(N*K)

 

++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Sorting 없이 Hash Key를 만들 수 있다면 Time complexity O(N*K) 로도 가능.

=> 각 alphabet letter의 개수만 구분되면 되기 때문에

int aLetterCount[26] 배열을 key로 한 hash table으로 각 anagram group을 구분 가능하다.

=> K 개의 letter 개수를 세는 것은 O(K) 시간이 걸리기 때문에 O(N*K).

 

 

원본 링크: https://leetcode.com/problems/group-anagrams/