LeetCode Top Interview 150) Group Anagrams

Question

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.

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

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

---

---

알파벳 소문자만 가지는 문자열을 원소로 가지는 리스트 strs가 있고, 애너그램 관계인 문자열끼리 다시 리스트로 묶은 리스트를 반환하는 문제입니다. 즉, 2차원 리스트를 반환하는 문제가 되겠습니다.
문제에서 반환할 리스트의 정렬 상태에 대한 얘기가 없었는데 실제로 원소만 맞으면 되는 문제인듯 합니다.

제가 생각한 코드는 다음과 같습니다.

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for s in strs:
            d[''.join(sorted(s))].append(s)
        return d.values()

• 문자열 : 문자열 리스트 키값쌍을 가지는 딕셔너리 d를 선언합니다. 이 때 키 문자열은 정렬된 문자열입니다. 애너그램 관계인 문자열끼리 파악하기위해 정렬된 상태가 같은지 비교하기 위해서입니다.
• strs를 탐색하며 원소인 s의 정렬된 문자열을 키, 해당 값 리스트에 s를 포함합니다.
  • ''.join(sorted(s)) : sorted(s)로 s의 정렬된 문자열리스트를 ''.join에 넘겨서 문자열리스트를 공백없이 이어붙인 문자열을 반환합니다.
• 반복문이 끝난 후 애너그램 관계인 문자열끼리 같은 리스트에 딕셔너리 값으로 남아있으므로 딕셔너리의 값을 반환합니다.

---

애너그램 관계를 문자열 정렬로 비교하고, 리스트로 바로 포함시켜 주었습니다.

가독성을 위해 문자열 정렬 비교 부분을 파이토닉하게 작성했지만, 딕셔너리 방식으로 비교하여 시간복잡도를 조금 더 최적화할 수 있습니다.