MediumLeetCode #49Arrays & Hashing

Group Anagrams

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

Constraints

1 <= strs.length <= 10^4, 0 <= strs[i].length <= 100

Examples

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Solution

Approach

Use sorted string as key in hash map. All anagrams will have the same sorted representation.

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))
        groups[key].append(s)
    return list(groups.values())

Complexity

Time:O(n * k log k)

Space:O(n * k)

Hints

1.How can you identify anagrams uniquely?
2.What if you sort each string?
3.Use a hash map with sorted string as key

Asked at

Google