Problem statement

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

Solution 1

First idea is to notice that if we have two anagrams, than when we sort symbols in each of them, then we will have exactly the same string. So we need for each string to sort it and then use defaultdict.

Complexity

Time complexity will be O(nk * log k), space complexity is O(nk).

Code

class Solution:
    def groupAnagrams(self, strs):
        t = defaultdict(list)
        for s in strs:
            t["".join(sorted(s))].append(s)
        return t.values()

Solution 2

Two strings are anagrams if and only if their character counts, that is frequencies of each letter a, b, ..., z are the same. So it can be done with defauldict(list), where key is 26-element list and values are strings, corresponding to this key.

Complexity

Time complexity is O(nk + 26n), where n is number of strings and k is the length of the biggest string. Space complexity is O(26n).

Code

class Solution:
    def groupAnagrams(self, strs):
        ans = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            ans[tuple(count)].append(s)
        return ans.values()