[LEETCODE] 49: Group Anagrams(Python)

Group Anagrams - LeetCode

문제 설명

같은 문자들로 이루어진 단어들을 묶어 보자.

나의 풀이

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d=dict()
        for i in strs:
            tmp=str(sorted(i))
            d[tmp]=d.get(tmp,[])+[i]
        answer=list(d.values())
        return answer

어떤 문자열에 대해 그 문자열의 기본형을 정렬된 상태라고 친다. 이런 정렬된 상태를 딕셔너리의 키 값으로 두고 같은 기본형을 가지는 문자열들을 한 묶음으로 묶는다.

시간복잡도

한 문자열의 길이는 최대 100이므로 정렬에는 O(100log100)이 걸린다. 실제 값으로 치환하면 약 O(102)인 것 같다. 또 문자열 개수만큼 반복해야 하므로 O(n)만큼 정렬을 반복한다. 따라서 전체 시간복잡도는 O(102*n) 즉 O(10**7)이다.