49. Group Anagrams

1. Description

• Given an array of strings strs, group the anagrams together. You can return the answer in any order.

2. Example

Example 1

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

Explanation

• There is no string in strs that can be rearranged to form "bat".
• The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
• The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2

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

Example 3

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

3. Solution

Note

• 제한시간 30분을 주고 풀었지만 풀지 못했다.

• 📌광성이가 풀어낸 방식을 이해하여 코드를 작성해보았다.

  • Runtime: 11ms
  • 설명
    • 첫번째 요소를 기준으로 말하자면 첫번째 요소를 정렬을 한다.
    • 정렬된 요소가 만든 딕셔너리에 없으면 정렬된 요소를 키값으로 지정하고 정렬되기 전 요소를 값으로 리스트 형태로 저장한다.
    • 정렬된 요소가 딕셔너리에 있다면 정렬된 요소를 키값으로 하는 리스트에 정렬되기 전 요소를 값으로 추가한다.
    • 딕셔너리의 값만 추출하여 빈 리스트에 넣고 리턴을 해준다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = []
        dic = {}
 
        for i in strs:
            sorted_str = ''.join(sorted(i))
 
            if sorted_str in dic.keys():
                dic[sorted_str].append(i)
            else:
                dic[sorted_str] = [i]
        
        for key, value in dic.items():
            ans.append(value)
        return ans

• 📌sorted()를 사용하면 문자열 형태가 리스트 형태로 변환이 된다.
  • sorted_str = ''.join(sorted(i))를 통해 리스트형태를 문자열로 바꿔준다.
• 📌딕셔너리의 값을 리스트 형태로 만들게 되면 값을 추가할 때 append()를 사용하면 된다.

s1 = s.sort() # wrong
s2 = sorted(s) # ['a','d','e','f'] 
s3 = ''.join(sorted(s)) # "adef"

4. What I Learned

References

Python Documentation/Dictionaries 문자열 정렬 딕셔너리에 새로운 키 생성 딕셔너리 하나의 key에 여러개 value 추가하기