LeetCode: Group Anagrams

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"]]

 

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

 

 

문제 리뷰를 시작하겠다!

 

 

이 문제는 단어에 해당하는 문자가 동일한 문자끼리 묶으면 되는 문제이다. 

 

나는 이 부분에 시간복잡도가 nlogn 인 merge sort를 사용하고 싶었다.

 

우선 문자를 정렬하기 위해서는 문자를 아스키 코드로 변환해야 한다. 

-> ord함수 사용

 

이후 merge sort를 구현하여 아스키 코드를 정렬한 값을 받아온다. 

 

여기서 이 값을 문자열로 바꿔 결과 딕셔너리 키 값으로 저장하는데, 만약 value에 아무것도 없다면 

-> dict.get(정렬 아스키 문자) == None 이라면

 

dict[정렬 아스키 문자] = [원본 단어] 

 

value가 있다면 dict[정렬 아스키 문자].append(원본단어) 를 사용하여 문자열을 추가시켜주었다. 

 

말로만 들으면 쉬울 것 같지만 세부적인 변수형을 맞추는 과정이 조금 까다로웠다.

 

사실 set을 이용하면 좀 더 쉽게 풀었을 것 같긴 하지만 암기한 merge sort를 사용해보고 싶어서 이렇게 구현해봤다. 

 

그래프 위치가 조금 슬프다.. 

 

그래도 sort를 직접 구현해보니까 좀 더 재미있는 것 같기도 하다.

 

이상 오늘의 포스팅을 마치겠다!

---

구현 코드

 

class Solution(object):
    def merge_sort(self, arr): # merge sort구현
        if len(arr) <= 1:
            return arr

        mid = len(arr)//2
        left = self.merge_sort(arr[:mid])
        right = self.merge_sort(arr[mid:])
        
        l = 0
        r = 0
        res = []
        while l < len(left) and r < len(right):
            if left[l] < right[r]:
                res.append(left[l])
                l += 1
            else:
                res.append(right[r])
                r += 1

        while l < len(left):
            res.append(left[l])
            l += 1
        while r < len(right):
            res.append(right[r])
            r += 1
        
        return res
    
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        
        res = {}
        for st in strs:
            temp1 = []
            for ch in st:
                temp1.append(ord(ch))
            temp2= self.merge_sort(temp1)
            if res.get(str(temp2)) == None: # 첫 등록된 단어 집합일 경우
                res[str(temp2)] = [st]
            else:
                res[str(temp2)].append(st) # 이미 등록된 단어 집합

        return list(res.values())