그룹 아나그램 파이썬 솔루션

Link to leetcode problem here

문제는 다음과 같습니다.
문자열 배열이 주어지면 아나그램을 함께 그룹화하십시오. 어떤 순서로든 답변을 반환할 수 있습니다.

Anagram은 일반적으로 모든 원래 문자를 정확히 한 번 사용하여 다른 단어 또는 구의 문자를 재배열하여 형성된 단어 또는 구입니다.

초기 생각

우리가 먼저 생각해야 할 것은 주어진 단어가 다른 단어의 아나그램인지 구별하는 방법입니다. 단어의 각 문자를 살펴보는 것이 우리의 솔루션을 위한 시작이 될 수 있습니다. 그러나 각 문자를 살펴보고 2개의 단어에 동일한 문자가 있는지 알아내는 것은 너무 오래 걸릴 수 있습니다.

각 글자를 단어의 알파벳순으로 정렬하면 어떨까요? 이것은 철자가 같고 아나그램인 단어를 가리킬 수 있습니다.

단어를 정렬하는 가장 좋은 방법은 정렬 방법입니다. 파이썬에서는 단어 자체에서 할 수 있습니다.sortedWord = "".join(sorted(word))다른 언어는 그렇게 친절하지 않을 수 있습니다.

이제 모든 단어를 정렬하여 자체 내에서 정렬할 수 있으므로 정렬된 단어를 동일하게 그룹화할 수 있습니다.
"eat, tea, ate"와 같은 단어는 모두 같은 "aet"로 정렬됩니다.

문제가 "그룹 아나그램"이라고 불리기 때문에 이것이 우리의 전체 솔루션은 아닙니다. 이 모든 개별 그룹을 어떻게 저장할까요?

우리가 "먹다, 먹다", "차"라는 단어가 모두 "aet"로 분류된다는 것을 알고 있기 때문입니다. 해시 테이블이나 사전에서 정렬된 단어로 그룹화하면 어떻게 될까요?
그러면 사전은 다음과 같이 보일 것입니다.

table = {
    "aet": ["ate", "eat", "tea"]
}

그러면 어떤 단어가 서로의 아나그램인지 확인할 수 있습니다. 예를 들어 "car"와 같은 다른 단어가 있는 경우."".join(sorted(car)) => acr
따라서 "aet"와 동일하지 않은 것은 다른 단어의 아나그램이 아닙니다.

새 단어가 있으므로 테이블에 새 키 값 쌍으로 추가할 수 있습니다.

table = {
    "aet": ["ate", "eat", "tea"],
    "acr": ["car"]
}

이것은 단어의 전체 입력 배열을 살펴볼 때까지 일반적인 패턴입니다.

문제는 아나그램 목록을 하나의 큰 배열로 함께 반환하도록 요청합니다. 그런 다음 anagram이 있는 배열 목록에서 테이블의 모든 값을 반환하는 파이썬에서 list(table.values())를 반환할 수 있습니다.

def groupAnagrams(words):
    anagrams = {}
    for word in words:
        sortedWord = "".join(sorted(word))
        if sortedWord in anagrams:
            anagrams[sortedWord].append(word)
        else:
            anagrams[sortedWord] = [word]
    return list(anagrams.values())