Problem 49

(Last updated: )

Question statement:

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Solution:

I have waited so long to use this trick! Last time there was an anagram problem on leetcode daily, I gave a solution based on comparing Counters. But then I saw a solution that just sorted all the words, and simply checked for equality. Now is the time to employ the same trick myself

Main idea:

Scan through strs, and sort strs[i] and append strs[i] to a (list) dictionary as a value corresponding to the key sorted(strs[i]). Return dictionary.values().

Code:

1
2
3
4
5
6
7
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    dic  = defaultdict(list)
    for i in range(len(strs)):
        sorted_word = ''.join(sorted(strs[i]))
        dic[sorted_word].append(strs[i])
    
    return dic.values()

Comments:

Time complexity: nklog(k) where n = len(strs), k = max(len(str[i])).

At the time of submission, the above solution passes leetcode submission cases in 78ms, beats 96.01% of users. It uses 20.26MB of memory, beating 69.69% of users.