Problem Description

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Example 2:

  • Input: strs = [""]
  • Output: [[""]]

Example 3:

  • Input: strs = ["a"]
  • Output: [["a"]]

My Idea

My initial idea was to use the sorting approach from [[242. Valid Anagram]]. This results in a time complexity of O(nklog(k), where k is the length of the longest string in strs. A more optimal approach is using a character frequency map to detect the anagrams, since this eliminates the need for sorting and results in a time complexity of O(nk).

My solution

# Optimal solution with time complexity of O(nk),
#where k is the max len of a string in strs
def groupAnagrams(strs: list[str]) -> list[list[str]]:
    d=dict()
    for s in strs:
        xs=[0]*26 # since we only have lower case English letters in the input
        for l in s:
            xs[ord(l)-ord('a')]+=1
        xs=tuple(xs)
        if xs in d:
            d[xs].append(s)
        else:
            d[xs]=[s]
    return [x for x in d.values()]
# Time complexity of O(nklog(k)) where k is the max len of a string in strs
def groupAnagramsInitial(strs: list[str]) -> list[list[str]]:
    d=dict()
    for s in strs:
        xs=str(sorted(s))
        if xs in d:
            d[xs].append(s)
        else:
            d[xs]=[s]
    return [x for x in d.values()]

print(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [["bat"],["nat","tan"],["ate","eat","tea"]]