LeetCode 49: Group Anagrams ·

Table of Contents

Meta Data
#

Difficulty: medium First Attempt: 2022-10-22

Submissions: Runtime Error → Wrong Answer ×2 → Time Limit Exceeded ×3 → Accepted → Runtime Error → Accepted ×3

Approach
#

Anagrams are identical after sorting, so use "".join(sorted(s)) (or tuple(sorted(s))) as the key (Hash Table Template 5) in a defaultdict(list) and return all values. A 26-length count tuple also works as a key and skips sorting.

My Attempts
#

This took 11 submissions:

Attempt 1 had a typo (rse, NameError); attempt 2 only searched existing groups and never created a new one, so it always returned an empty list.
Attempt 3 added new groups but used set to match them: ["bb", "b"] landed in one group.
Comparing with Counter fixed the answers, but each string was compared with every group, timing out three times.
Switching to “sorted string as key” passed. A 2022-10-27 rewrite wrote values instead of values() and raised one more RE.

Solution
#

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

Complexity
#

Time O(n · k log k) for string length k, space O(nk).

Mistakes to Avoid
#

Sets do not work: "bb" and "b" share a character set but are not anagrams.
Comparing each string with every existing group is O(n²) and times out; a key finds the group directly.
dict.values is a method and needs parentheses.

Interview Explanation
#

I key a hash map by each string’s sorted form, so anagrams share a key, and return the groups. Time O(n · k log k); for long strings a 26-letter count tuple can be the key instead.