[LeetCode/Python] 49. Group Anagrams

📌 Problem

[LeetCode] 49. Group Anagrams

📌 Solution

Solution 1: Sorted Key

Idea

If two strings are anagrams, they contain the same characters.
When you sort the characters, they become the same string, so they can be grouped using the same key.

anagram이면 같은 문자들을 가지고 있음 → 정렬하면 동일한 문자열이 됨 → 같은 key로 묶임

Code

from collections import defaultdict
from typing import List

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

        for w in strs:
            key = "".join(sorted(w))  # "eat" -> ['a', 'e', 't'] -> "aet"
            groups[key].append(w)

        return list(groups.values())

defaultdict

• key가 처음 등장해도 자동으로 빈 리스트 []를 만들어주는 dict
• if key not in groups: groups[key]=[] 같은 코드를 따로 안 써도 됨.

1. groups = defaultdict(list)
groups[key]를 처음 접근하면, 자동으로 []를 만들어서 넣어둔다.
   즉,groups["aet"]가 없는데 groups["aet"].append("eat") 하면 자동으로 groups["aet"] = []가 만들어진 뒤 append 됨.

2. key = "".join(sorted(w)): anagram signature 만들기

   • sorted(w): sorted()는 문자열을 문자 단위로 쪼개서 정렬한 리스트를 반환

     w = "eat" → sorted(w) → ['a', 'e', 't']

   • .join: sorted(w)의 결과는 리스트이므로 dict key로 사용하기 위해서 문자열로 변경

     ['a','e','t'] → "aet"

Time Complexity

• Time Complexity: $O(n * k log k)$ (where $k$ is the length of each word)
• Space Complexity: $O(n * k)$ (space used to store all grouped words)

Solution 2: Count Key

Idea

If two strings are anagrams, they have exactly the same frequency of each character.

anagram이면 “각 알파벳이 몇 번 나왔는지”가 완전히 같다.

Code

from collections import defaultdict
from typing import List

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

        for w in strs:
            count = [0] * 26
            for ch in w:
                count[ord(ch) - ord('a')] += 1

            key = tuple(count)
            groups[key].append(w)

        return list(groups.values())

1. count[i] = 해당 알파벳이 나온 횟수

2. ord(ch): 문자의 아스키/유니코드 코드값(정수) 반환
   ord(ch) - ord('a')는 문자를 0~25 인덱스로 바꾸는 작업:

   • ch='a' → 97-97 = 0
   • ch='c' → 99-97 = 2
   • ch='t' → 116-97 = 19

3. key = tuple(count): 딕셔너리 key는 변하면 안 되는 값(immutable) 이어야 함
   리스트 count는 mutable(값 변경 가능) → dict key로 사용 불가 ❌
   튜플은 immutable → dict key로 사용 가능 ✅
   그래서 리스트를 튜플로 “고정”해서 key로 사용

Complexity

• Time Complexity: $O(n * k)$
  (Each word is processed once, counting characters in linear time)
• Space Complexity: $O(n * k)$
  (All input strings are stored in the grouped output; count keys use constant space per group)