[Python, algorithm] 애너그램(Anagram)

출처: 파이썬 알고리즘 인터뷰

 

문제: 애너그램, 문자의 위치만 바뀌었을 때 같은 단어를 만들 수 있음.

 

1. dictionary에 존재하지 않는 키를 삽입하면 error가 발생하기 때문에 defluat를 생성한다.

anagrams = collections.defaultdict(list)

 

2. 각 단어를 sorted()를 통해 정렬 후 다시 join하여 key 생성

print( sorted('abc'))
print( sorted('bca'))

print( ''.join(sorted('abc')))
print( ''.join(sorted('bca')))

 

즉, 아래와 같이 'abc'와 'bca'는 같은 key를 생성한다.

print:

['a', 'b', 'c']
['a', 'b', 'c']
abc
abc

 

3. 해당 dictionary에서 value()를 사용해서 value만 추출한다.

anagrams.values()

둘의 차이는 아래와 같다.

print(anagrams)
print(anagrams.values())

print:

defaultdict(<class 'list'>, {'abc': ['abc', 'bac', 'cab'], 'ert': ['ert', 'etr']})
dict_values([['abc', 'bac', 'cab'], ['ert', 'etr']])

 

완성된 코드

def group_anagrams(strs: [str]) -> [[str]]:
    anagrams = collections.defaultdict(list)

    for word in strs:
        anagrams[''.join(sorted(word))].append(word)   
    return anagrams.values()