49. Group Anagrams

https://leetcode.com/problems/group-anagrams/

Python

Group by custom key

• Time: O(2N)
• Space: O(N+M), which M is the final group number

from collections import defaultdict, Counter


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)

        for string in strs:
            key = self.gen_key(string)
            groups[key].append(string)

        return list(groups.values())

    @staticmethod
    def gen_key(string):
        """
        return: str, which "{char}{count}" * n, with sorted char order
            ate => "a1e1t1"
            eel => "e2l1"
        """
        counts = Counter(string)
        sequence = []
        for char in sorted(counts.keys()):
            sequence.append(char)
            sequence.append(str(counts[char]))
        return ''.join(sequence)