Group Anagrams

Problem

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.

For example:

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

Solution

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        _map = {}
        
        for i in strs:
            sorted_word = ''.join(sorted(i))
            if sorted_word not in _map:
                _map[sorted_word] = [i]
            elif sorted_word in _map:
                _map[sorted_word].append(i)
        return list(_map.values())
        
#anagrams will map to the same string if characters in
#the string are sorted

#we're going to iterate through the array of words and
#at each word, sort the letters and check if that 
#sorted word exists in the hash map


#Time: O(w*n*log n) where w is the number of words and
#n is the length of the longest word
#Space: O(w*n)