[LeetCode]Group Anagrams

https://leetcode.com/problems/group-anagrams/description/

Group Anagrams - LeetCode

 

문제 분석

주어진 문자열에서 동일한 anagram을 그룹화 하는 문제입니다.

 

처음 시도한 답안 - 실패

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        answers = [[strs[0]]]

        for word in strs[1:]:
            for idx, answer in enumerate(answers):
                if set(answer[0]) == set(word):
                    if word == answer[0] and (0 <= len(word) <= 1):
                        answers[idx].append(word)
                        break
                    if word not in answers[idx]:
                        answers[idx].append(word)
                        break
                else:
                    if idx != len(answers)-1:
                        continue
                    else:
                        answers.append([word])

        return answers

접근 방법

1. 문자열 리스트를 순회합니다.
2. answers 리스트를 순회하면서 동일한 anagram 그룹인 경우 해당 인덱스의 리스트의 요소로서 추가합니다.
3. 동일한 그룹이 아닌경우는 answers에 새로운 요소로서 추가합니다.

직관적으로 반복을 순회하면서 그룹화를 하려고 했지만, 그룹화를 하려는 과정에서 여러가지 예외 케이스가 많이 발생하게 되었고 커버하기 위한 조건문을 계속해서 추가해도 여전히 실패하는 코드였습니다.

 

두번째로 시도한 답안

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 해시 테이블에 key로 그룹화 될 anagram, value로 그룹화 된 목록들을 저장합니다.
        hash_table = {}

        for word in strs:
            # 등장하는 단어를 정렬합니다. 정렬을 함으로써 동일한 anagram 그룹인지 판단할 수 있습니다.
            sorted_word = ''.join(sorted(word))

            # 동일한 anagram 그룹이 아니라면
            if sorted_word not in hash_table:
                hash_table[sorted_word] = [word]
            # 동일한 anagram 그룹이라면
            else:
                hash_table[sorted_word].append(word)

        return list(hash_table.values())

접근 방법

1. 해시 테이블을 이용해서 key로는 그룹화 될 anagram, value로는 그룹화 되어있는 목록들을 저장합니다.
2. 문자열을 순회합니다.
3. anagram인지 판별하는 것은 등장하는 문자를 정렬함으로써 판별이 가능합니다.
4. 이미 있는 anagram 그룹이라면 해당 value의 요소로서 추가합니다.
5. 존재하지 않는 anagram 그룹이라면 새롭게 추가합니다.
6. 저장되어있는 values 들을 리스트해서 포맷에 맞게 return 합니다.

반복을 마친 Hash table 값은 다음과 같습니다.

{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

 

저는 set()을 통해서 anagram을 판별하려고 하였으나 여러가지 예외 케이스를 많이 마주했습니다. 솔루션에서는 정렬을 통해서 동일한 anagram인지 판별하고 있었는데 굉장히 놀라웠습니다. 또한, 해시 테이블이 이렇게 활용될 수도 있다는 점도 배울 수 있었습니다.