algoadvance

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"]]

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lower-case English letters.

Clarifying Questions

1. Can the input list contain empty strings?
   • Yes, as mentioned in the problem statement.
2. Can the input list contain strings of varying lengths?
   • Yes, each string can have a different length, but it’s only up to 100 characters.
3. Is the output order of the groups or within the groups important?
   • No, the order is not important as long as the anagrams are grouped together.

Strategy

1. Use a Hash Map:
   • We will create a dictionary where the keys are tuples of sorted characters of a string, and the values are lists of strings which are anagrams.
   • Sorting the string itself can be used to check if strings are anagrams because anagrams will result in identical sorted strings.
2. Iterate Through Each String:
   • Sort each string and use it as the key in the dictionary.
   • Append the original string to the list corresponding to the sorted tuple key.
3. Compile the Result:
   • Extract the lists from the dictionary and return them as the result.

Example Walkthrough

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

• After sorting the strings:
  • “eat” => “aet”
  • “tea” => “aet”
  • “tan” => “ant”
  • “ate” => “aet”
  • “nat” => “ant”
  • “bat” => “abt”
• Grouping them in the dictionary (key => value):
  • “aet” => [“eat”, “tea”, “ate”]
  • “ant” => [“tan”, “nat”]
  • “abt” => [“bat”]
• Result: [[“eat”, “tea”, “ate”], [“tan”, “nat”], [“bat”]]

Code

def groupAnagrams(strs):
    from collections import defaultdict
    anagrams = defaultdict(list)

    for s in strs:
        sorted_str = tuple(sorted(s))
        anagrams[sorted_str].append(s)

    return list(anagrams.values())

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

Time Complexity

• Sorting each string: (O(K \log K)) where (K) is the maximum length of a string in strs
• Overall: If there are (N) strings each with maximum length (K), the total time complexity is (O(N \times K \log K))

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?