LeetCode 49: Group Anagrams

To group anagrams, we need a group id against which we can collect the anagrams.

Sort

Since all anagrams are identical after sorting, we can use sorted anagram as the group id.

If there are $n$ strings and the longest string has length $m$ , time: $\mathcal{O}(n \cdot m \cdot \lg{m})$ , space: $\mathcal{}(n \cdot m)$ .

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for s in strs:
            id = "".join(sorted(s))
            groups[id] = groups.get(id, []) + [s]
        
        return [
            g for g in groups.values()
        ]

Character frequency

Sequence of character counts, in alphabetic order, is same for all anagrams. Since the alphabet size is 26, we can use the sequence of 26 counts as the group id.

Time: $\mathcal{O}(n \cdot m)$ , space: $\mathcal{O}(n \cdot m)$ .

class Solution:
    def frequency_signature(self, s):
        freq = [0] * 26
        for c in s:
            i = ord('a') - ord(c)
            freq[i] += 1
        
        return tuple(freq)

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for s in strs:
            id = self.frequency_signature(s)
            groups[id] = groups.get(id, []) + [s]
        
        return [
            g for g in groups.values()
        ]

unreasonably effective