Python | Group Anagrams from given list

Anagrams are words that are formed by similar elements but the orders in which these characters occur differ. Sometimes, we may encounter a problem in which we need to group the anagrams and hence the solution to the above problem always helps. Let’s discuss certain ways in which this can be done.

Method #1 : Using defaultdict() + sorted() + values()

The combination of the above functions can be used to get the solution to the above problem. In this, we first get the anagrams grouped using defaultdict and use the sorted function to get each anagram root value to group anagrams.  

The original list : ['lump', 'eat', 'me', 'tea', 'em', 'plum']
The grouped Anagrams : [['me', 'em'], ['lump', 'plum'], ['eat', 'tea']]

Time Complexity: O(nlogn), where n is the length of the input list. This is because we’re using defaultdict() + sorted() + values() which has a time complexity of O(nlogn) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list.

Method #2 : Using list comprehension + sorted() + lambda + groupby()

The combination of above function can also be used to perform this particular task. The groupby function performs the necessary grouping together. The lambda function helps to group alike anagrams.

The original list : ['lump', 'eat', 'me', 'tea', 'em', 'plum']
The grouped Anagrams : [['me', 'em'], ['lump', 'plum'], ['eat', 'tea']]

Time Complexity: O(n*nlogn), where n is the length of the input list. This is because we’re using  list comprehension + sorted() + lambda + groupby() which has a time complexity of O(n*nlogn) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list.

Method3: Using Simple Python Programming

Below is the program to group anagram words together in a simple python programming way. Without using list comprehension or lambda or imported methods.

The method followed is simple – 

• Sort each word and use the sorted word as a dictionary key
• Keep adding new word into dictionary against sorted key

Output:

In dictionary format
{'aet': ['eat', 'ate', 'tea'], 'ant': ['ant', 'tan'], 'abt': ['bat'],
 'abdeo': ['adobe', 'abode'], 'eilnst': ['listen', 'silent']}
 
In list format
[['eat', 'ate', 'tea'], ['ant', 'tan'], ['bat'], ['adobe', 'abode'], ['listen', 'silent']]

Method#4: Using a dictionary to group anagrams

Approach:

we can use a dictionary to group the anagrams. We will iterate through the given list of words, sort each word and use the sorted word as a key in the dictionary. The value of each key will be a list of anagrams. Finally, we will return the values of the dictionary as the grouped anagrams.

Algorithm:

1. Initialize an empty dictionary called anagram_dict to store the anagrams.
2. Loop through each word in the input list of words.
3. Sort the characters in the word and join them together to form a new string, which will be used as a key in the dictionary.
4. Check if the key already exists in the dictionary.
5. If the key already exists, append the word to the value list of the corresponding key.
6. If the key does not exist, create a new key with the sorted word as the key and a new list with the word as the only element as the value.
7. After iterating through all the words, return the values of the anagram_dict dictionary as a list of lists, where each sublist contains the anagrams of a group.

Example

[['lump', 'plum'], ['eat', 'tea'], ['me', 'em']]

Time Complexity: O(n * klogk), where n is the number of words in the list and k is the length of the longest word.

Auxiliary Space: O(n*k), as we are using a dictionary to store the anagrams.

Method #5: Using Counter() + tuple() + sorted()  and dictionary

Step by step Algorithm: 

1. Create an empty dictionary anagrams.
2. Iterate through each word in the input list words.
3. Create a Counter object for the word.
4. Convert the Counter object to a tuple of (element, count) pairs and sort it.
5. Use the sorted tuple as the key to store the word in the anagrams dictionary.
6. If the key already exists in anagrams, append the word to its corresponding list.
7. If the key doesn’t exist, create a new list with the word and store it in the anagrams dictionary.
8. Return the list of values from the anagrams dictionary.

The original list : ['lump', 'eat', 'me', 'tea', 'em', 'plum']
The grouped Anagrams : [['lump', 'plum'], ['eat', 'tea'], ['me', 'em']]

Complexity Analysis:

Time Complexity: O(n * k log k), where n is the number of words and k is the maximum length of a word.

Auxiliary Space: O(n * k), where n is the number of words and k is the maximum length of a word.

Method #6: Using sets and list comprehension to group anagrams 

• Define a function group_anagrams that takes in a list of words.
• Use list comprehension to create a set unique_words of the unique sorted words from the input list words.
• Use another list comprehension to create a list of lists anagrams where each list contains all the words from the input list that are anagrams of each other.
• Return the list of anagram lists.
• Call the group_anagrams function with the sample input words.
• Print the output of the function.

The original list : ['lump', 'eat', 'me', 'tea', 'em', 'plum']
The grouped Anagrams : [['lump', 'plum'], ['me', 'em'], ['eat', 'tea']]

The time complexity of this approach is O(nmlog(m)), where n is the number of words in the list and m is the maximum length of a word in the list. 

The space complexity of this approach is O(nm), as we need to store all the words in the dictionary.