> 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()
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/string/49group-anagrams.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.