[Leetcode] Group Anagrams - 파이썬

문제링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

접근방법

해당문제는 입력받은 배열에서 철자가 같은 문자열끼리 묶어 이중배열로 return 해주는 문제였습니다.

 

10^4이라서 O(N)의 접근법이 필요합니다.

길이가 0과 1인 입력은 따로 처리를 해주었습니다.

 

이 문제의 관건은 해당 문자열이 들어왔을때 정렬을 하여 그 정렬된 문자열이 입력이 되었었는지 최소한의 시간복잡도로 확인하는 것이 관건이였습니다.

 

ex)

“aaw” ,”waa” , “ww” 가 입력일시

“aaw”,”waa”는 정렬을 통해 “aaw”로 변경해서 memo에 저장한다음

그 memo안에 값을 정렬하여 return하는 문제였습니다.

 

풀이코드

 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if len(strs) == 0:
            return [[""]]
        if len(strs) == 1:
            return [strs]

        memo = {}
        answer = []

        # strs를 for문으로 반복하면서 해당 문자와 철자가 같은 문자열로 묶어줘야한다
        for char in strs:
            new_char = sorted(char)
            now_char = ""
            for i in new_char:
                now_char += i
            # 만약 memo에 없으면(처음 나오는 값이면 memo에 저장)
            if now_char not in memo:
                memo[now_char] = [char]
            else:
                tmp = memo[now_char]
                tmp.append(char)
                memo[now_char] = tmp

        for i in memo:
            answer.append(sorted(memo[i]))

        
        return answer