[파이썬 알고리즘 인터뷰][문자열] 그룹 애너그램 (중요)

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

• 애너그램
  • 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 의미
  • 문자의 순서가 바뀌면 같아지는 단어들끼리 묶은 리스트 반환

 

책에서 구현된 코드

def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
    anagrams = collections.defaultdict(list)
    
    for word in strs:
        anagrams[''.join(sorted(word))].append(word)
    
    return list(anagrams.values())

 

기억해야할 기법

• frozenset을 dict의 key로 사용시 주의
  
  • 문자의 개수를 생략하기 때문에, 사용된 알파벳이 같으면 같은 단어 취급

 

내가 구현한 코드

from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
    dict_anagrams = defaultdict(list)
    for word in words:
        dict_anagrams[frozenset(list(word))].append(word)
    return list(dict_anagrams.values())

• 접근은 나쁘지 않았던 거 같은데... 리트코드에서 실패
  • frozenset은 사용한 알파벳 종류만 확인하고 개수는 무시