Group Anagrams

class Solution:

    # Runtime: O(n * mlogm), where n is len of strs, and m is len of longest word
    # Space: O(nm)
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Groups is a dict where key is sorted str and value is list of strings from strs that are anagrams of sorted str
        groups = {}

        # For s in strs
        for s in strs:
            # Generate a sorted version of s. Strings that are anagrams should have the same sorted version.
            sorted_s = ''.join(sorted(s))
            # If s matches any group, add s to group
            if sorted_s in groups:
                groups[sorted_s].append(s)
            # Else, create new group with s in it
            else:
                groups[sorted_s] = [s]

        # Convert groups to list and return group lists
        group_lists = []
        for sorted_str, str_group in groups.items():
            group_lists.append(str_group)
        return group_lists