> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/string/49group-anagrams.md).

# 49\_Group Anagrams

Level: medium

Tag: string, hash table

## Question

```
Given an array of strings, group anagrams together.

Example:
Given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.
```

## Idea

1. **With sort.** Create a dictionary to store sorted non-duplicated elements as keys, and corresponding items in the strs list as values. Keys should be tuple, because tuple is immutable but list is mutable. After sorting a string, the result is a list. So we need to transfer the list to tuple. Values are stored in list. ![](/files/-M2dslqmmUa8ezu2Up7T)
2. **Without sort, use count table.** Create a dictionary to store count table as keys, corresponding items in the strs list as values. We need to transfer the count table to tuple as well.![](/files/-M2dslqodPEyQwjKq1Wl)

## Complexity 1 (with sort)

* Time Complexity: $$O(nklogk)$$ , where `n` is the length of `strs`, and `k` is the maximum length of a string in `strs`. The outer loop has complexity $$O(n)$$ as we iterate through each string. Then, we sort each string in $$O(klogk)$$ time.
* Space Complexity: $$O(nk)$$ , the total information content stored in`ans`.

## **Complexity 2 (without sort, use count table)**

* Time Complexity: $$O(nk)$$ , where `n` is the length of`strs`, and `k` is the maximum length of a string in`strs`. Counting each string is linear in the size of the string, and we count every string.
* Space Complexity: $$O(nk)$$ , the total information content stored in`ans`.

## Solution 1 (with sort)

```python
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """

        dic = {}

        for item in strs:
            sortedItem = tuple(sorted(item))   # must use tuple instead of list as output of sorted()
            if dic.get(sortedItem) == None :
             dic[sortedItem] = [item]          # set up type of dic.values as list before append elements
            else :
             dic[sortedItem].append(item)           
        return dic.values()
```

## Solution 2 (**without sort, use count table**)

```python
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """

        dic = {}

        for item in strs :
            countTable = [0]*26     # create count table to store frequency of 26 letters
            for letter in item :
                countTable[ord(letter) - ord("a")] += 1   # count frequency for each item in strs
            if dic.get(tuple(countTable)) == None :
                dic[tuple(countTable)] = [item]
            else :
                dic[tuple(countTable)].append(item)
        return dic.values()
```