파이썬 알고리즘 인터뷰 6장 5번 Group anagrams (리트코드 49번)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

주어진 문자열을 아나그램 단위로 묶어라.

아나그램이란 한 단어를 구성하는 글자를 그대로 유지하면서 순서만 바꾼 단어를 의미한다.

Solution

1차 - Time out

from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = []
        for word in strs:
            word_split = sorted(word)

            flag = False
            for group in result:
                if sorted(group[0]) == word_split:
                    group.append(word)
                    flag = True
            if not flag:
                result.append([word])
                
        return result

주어진 글자를 알파벳 순서로 정렬한 리스트를 만들고 해당 리스트 단위로 그룹핑을 진행하였다. 리스트는 hashable하지 않아서 dictionary의 키로 사용할 수 없다. 따라서 그냥 리스트를 돌면서 진행을 해버렸다.

for 문을 이중으로 돌면서 sorted까지 해버리니 시간 복잡도가 계산상 O(n^3)인듯 하다.

2차

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result_dict = {}
        for word in strs:
            word_split = sorted(word)
            sorted_word = "".join(word_split)

            if sorted_word in result_dict.keys():
                result_dict[sorted_word].append(word)
            else:
                result_dict[sorted_word] = [word]

        return list(result_dict.values())

list를 돌면서 group을 찾는 것이 아닌 dictionary의 키 값으로 찾기 위해 생각하다가 해당 그룹의 대표 글자를 생성하여 키 값으로 넣었다. 대표문자는 알파벳 순서로 정렬한 문자열로 하였다. 주어진 글자를 재정렬한 대표문자 형태로 만들고 dictionary에서 키 값으로 서치하여 시간 복잡도를 낮추었다.

Result

Reference

https://wiki.python.org/moin/TimeComplexity