---
tags: data_structure_python
---

# Group Anagrams <img src="https://img.shields.io/badge/-medium-orange">

Given an array of strings, group anagrams together.

<ins>**Example:**</ins>

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

**Note:**

- All inputs will be in lowercase.
- The order of your output does not matter.

# Solution

### Solution 1:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # n: total # of elements in strs.
        # k: maximum length of a string in strs.
        # Time complexity: O(nlog(n))
        # Space complexity: O(n).
        ans = collections.defaultdict(list)
        for word in strs:
            ans[tuple(sorted(word))].append(word)
        return ans.values()

### Solution 2:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # n: total # of elements in strs.
        # k: maximum length of a string in strs.
        # Time complexity: O(n).
        # Space complexity: O(n).
        ans = collections.defaultdict(list)
        for word in strs:
            count = [0]*26
            for char in word:
                count[ord(char) - ord('a')] += 1
            ans[tuple(count)].append(word)
        return ans.values()