:orphan:

Group Anagrams
==============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/group-anagrams/

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

 

**Example 1:**

.. container:: example-block

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

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

   **Explanation:**

   - There is no string in strs that can be rearranged to form
     ``"bat"``.
   - The strings ``"nat"`` and ``"tan"`` are anagrams as they can be
     rearranged to form each other.
   - The strings ``"ate"``, ``"eat"``, and ``"tea"`` are anagrams as
     they can be rearranged to form each other.

**Example 2:**

.. container:: example-block

   **Input:** strs = [""]

   **Output:** [[""]]

**Example 3:**

.. container:: example-block

   **Input:** strs = ["a"]

   **Output:** [["a"]]

 

**Constraints:**

- ``1 <= strs.length <= 10``\ :sup:```4```
- ``0 <= strs[i].length <= 100``
- ``strs[i]`` consists of lowercase English letters.

.. highlight:: python

Pattern
-------
Array, Hash Table, String, Sorting

Solution
--------
We can check whether 2 strings are anagrams by counting the number of each
letter in a dictionary. If the 2 strings are anagrams, then the dictionaries
will be equal. For each string, check whether it is an anagram of any of the
existing groups. If so, add it to that group. Otherwise, create a new group. To
save time on dictionary creation, we store a dictionary for each group.

Code
----

.. literalinclude:: ../problems/medium/group-anagrams/group_anagrams__approach_1.py
    :language: python
    :lines: 11-

Test
----
>>> from group_anagrams__approach_1 import groupAnagrams
>>> groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
>>> groupAnagrams([""])
[['']]
>>> groupAnagrams(["a"])
[['a']]

Complexity
----------
| :math:`n` is the number of strings in the input array, :math:`k` is the
maximum length of a string in the input array, and :math:`g` is the number of
groups
| Time: :math:`O(nkg)` — compare each string to groups
| Auxiliary Space: :math:`O(kg)` — store frequency dictionary for each
group

.. autofunction:: group_anagrams__approach_1.groupAnagrams