49. Group Anagrams

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

Group Anagrams - LeetCode

주어 word들을 똑같은 알파벳들 가지고있는것끼리 묶어 반환하는문제,

---

SOLUTION CODE

# PYTHON

 

1. key:value <=> word정렬값(sorted):original word

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = collections.defaultdict(list) # 빈 리스트

        # 각 단어를 정렬한값을 키로사용
        # 원래단어를 value로 사용
        for word in strs:
            # 파이썬은 list는 키값이될수없음.
            # 따라서 join을 사용해 str키값으로 반환
            anagrams[''.join(sorted(word))].append(word) 
        return list(anagrams.values())

 

2. key:value <=> word count:original word

: 이렇게하면 해당 O(M*N)의 시간복잡도를 가져 sorted보다 더 효율적으로 처리 가능하다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list) # 반환할 리스트

        for s in strs:
            count = [0] * 26 # a ... z

            for c in s: # 각 s당
                count[ord(c) - ord("a")] += 1 #나온 글자 횟수 카운팅
            # 키:글자횟수 value:original해당글자.
            #python에선 list가 키값 안되므로 tuple반환
            res[tuple(count)].append(s) 

        return res.values()

 

# C++

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

        vector<vector<string>> ans;

        unordered_map<string, vector<string>> mp;

        
         /*
                Consider example 1 : strs = ["eat","tea","tan","ate","nat","bat"]
                
                After the below opeartion of for loop map will contain
                
                aet -- eat, tea, ate
                ant -- tan, nat
                abt -- bat
        */

        /*
        키값은 str정렬해서 넣고, value는 original word
        */

        for(int i = 0; i < strs.size() ; i++){

            string s = strs[i];
            sort(strs[i].begin(),strs[i].end());
            mp[strs[i]].push_back(s);

        }

        //now simply put the elements  of second column of map in ans
        for(auto i : mp)
        {
            ans.push_back(i.second);
        }

        return ans;
    }
};

---

●Join은 list 를 문자열 Str로 반환한다.

 

●sort,sorted차이?

sort 함수는 리스트명.sort( ) 형식으로 "리스트형의 메소드"​​이며 리스트 원본값을 직접 수정

sorted 함수는 sorted( 리스트명 ) 형식으로 "내장 함수"이며 리스트 원본 값은 그대로이고 정렬 값을 반환