from collections import defaultdict

# Gotcha 1: there is no sort for strings.
# You have to convert the word to a list, then sort it using list.sort(),
# then reconstruct the string using ''.join(sorted_list)

# Gotcha 2: defaultdict is part of the collections library

class Solution(object):
    # Time: O(n * k * log k) where n is the number of words, and k is the length of the longest word
    # Space: O(n * k) to hold the result - k * n is the total number of characters
    def group_anagrams(self, words):
        """
        :type words: List[str]
        :rtype: List[List[str]]
        """

        sorted_dict = defaultdict(list)

        for word in words:
            letter_list = list(word) # or [c for c in word]
            letter_list.sort()
            sorted_word = ''.join(letter_list)
            sorted_dict[sorted_word].append(word)
        
        return list(sorted_dict.values())

solution = Solution()
print(solution.group_anagrams(['bat', 'car', 'atb', 'rca', 'aaa']))