[LeetCode] 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.

---

문제 풀이

문제 접근

1. 단어의 길이가 최대 100이고 단어 리스트의 최개 길이가 10^4 이다. 
2. 단어의 길이가 크지 않기 때문에, N^2 시간복잡도 내에 풀어되 될 듯하다.

풀이

1. 아나그램인지 확인하려면 단어의 알파벳이 일치하는지 확인해야한다.
2. 정렬을 사용하면 모든 문자의 알파벳들을 비교해볼 수 있다. 
3. 매 단어를 정렬하여 딕셔너리 리스트에 넣는다. 
4. 답을 반환할때는 리스트로 반환한다. 

소스 코드

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