[리트코드/파이썬] 49. Group Anagrams (문자열, 딕셔너리)

[리트코드/파이썬] 49. Group Anagrams (문자열, 딕셔너리) 

49. Group Anagrams

Medium

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.

 

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

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

---

[내 풀이]

※ 소요시간 : 5 분

※ 풀이 전략

- 같은 그룹의 알파벳을 분류하기 위해 sorted(x)

- 딕셔너리로 같은 분류(key)를 갖는 값들을 정리  

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = dict()
        # 같은 문자로 구성되었으면 같은 그룹
        for x in strs:
            sorted_x = ''.join(sorted(x))
            groups[sorted_x] = groups.get(sorted_x, []) + [x] 
        # 같은 그룹끼리 묶어 리턴
        return list(groups.values())

 

※ 중요 포인트

- groups.values() 만 하면 안 되고, list( )로 한 번 값을 정리 해주어야 한다. 

 

※ 다시 풀기

- defaultdict 써서 다시 풀기 

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        # 같은 문자로 구성되었으면 같은 그룹
        for x in strs:
            groups[''.join(sorted(x))].append(x)
        # 같은 그룹끼리 묶어 리턴
        return list(groups.values())

 

---

[다른 사람의 풀이]

※ 풀이 전략

- 나와 같다.

from collections import defaultdict

strs = ["eat","tea","tan","ate","nat","bat"]

anagrams = defaultdict(list)
for word in strs:
    anagrams["".join(sorted(word))].append(word)
    
return list(anagrams.values())

 

※ 중요 포인트

- defaultdict은 존재하지 않는 키를 삽입하려해도 error가 나지 않는 딕셔너리

- 따라서, defaultdict 를 쓰면 굳이 groups.get( ) 을 쓰지 않아도 된다.