Group Anagrams LeetCode

Group anagrams LeetCode problem is a fairly simple coding challenge asked during interviews. It assesses a coder’s understanding of anagrams, string manipulation, and effective usage of data structures. This LeetCode problem requires us to form groups of words that are anagrams of each other. An anagram, by definition, is a word or phrase that is obtained by rearranging the letters of an entirely different word or phrase by utilizing all of the letters only once. Note that these words or phrases have the same letters, thus making it possible to rearrange them and form two completely different words or phrases. We’ll solve this problem later on using Python.

Problem statement

We are provided with an array containing strings listOfStrings. We must group all anagrams — in short words or phrases given in a different order — returning the answer in any order. While solving this challenge, there are certain constraints that we need to keep in mind. They are stated as follows.

Constraints:
${1 <= listOfStrings.length <= 10^4}$
${1 <= listOfStrings[i].length <= 10^4}$
${listOfStrings[i]}$ will only contain lowercase letters form the English alphabet

Please go through the slides below to better understand what we must do.

Algorithm to solve group anagrams problem

To solve this problem, we will use a very simple approach. We will iterate over the entire list of strings and sort each word; the sorted representation of each word will be unique unless we encounter an anagram of that word/phrase, in which case both these words/phrases will have the same sorted representation. After sorting the word, we will store the sorted representation of that word as a key in a dictionary and the word itself as the value. We’ll get the same sorted representation whenever we encounter an anagram of the stored word. Thus, the anagram will be stored alongside that word for the same key in the dictionary. This is the gist of the algorithm used. Let’s take a detailed look at the steps.

We’ll create an empty dictionary that will store the list of grouped anagrams as values and their sorted representations as keys.
We’ll iterate the list of strings: listOfStrings.
As we iterate over each word, we sort it.
We then append the sorted representation of this word as a key and the original word as a value in the empty dictionary.
The values of the dictionary contain separate lists of all the grouped anagrams. We’ll return all the values of this dictionary as a single list.

from collections import defaultdict
#function which groups anagrams 
def groupAllAnagramsLeetcode(listOfStrings):
    #create a defaultdict object
    allMyAnagramsDictionary = defaultdict(list)
        
    for i in range(len(listOfStrings)):
        stringWord = listOfStrings[i]
        #sort the word 
        sortedRepresentation = ''.join(sorted(stringWord))
        #append the sorted representation as key and original word as value
        allMyAnagramsDictionary[sortedRepresentation].append(stringWord)
    listAnagrams = list(allMyAnagramsDictionary.values())
    return listAnagrams
# Test code: update listOfStrings as you like :)
if __name__ == "__main__":
    listOfStrings = ["dictator","tea","eat","tame","team","reckoning", "storm"]
    print(groupAllAnagramsLeetcode(listOfStrings))

Code explanation

Line 1: We’ll import defaultdict from the collections library. We need this to create a defaultdict object that will store lists of grouped anagrams.
Lines 4–7: Next, we create the function groupAllAnagramsLeetcode that receives the list of all words/phrases called listOfStrings as an argument. We also initialize a defaultdict object called allMyAnagramsDictionary to store the lists of grouped anagrams.
Lines 9–12: Then we iterate over the list listOfStrings and store the string obtained in the variable stringWord. This word will be sorted, and its sorted representation will be stored in sortedRepresentation
Line 14: The sorted representation, sortedRepresentation, and the original word corresponding to this variable will be appended to the dictionary, allMyAnagramsDictionary, as a key-value pair. As discussed above, the dictionary values contain all the grouped anagram lists.
Lines 16–17: Finally, we’ll nest all the values from the dictionary into another list using list(allMyAnagramsDictionary.values()) and return this nested list called listAnagrams.
Lines 20–22: This final section contains the driver code to call the groupAllAnagramsLeetcode function and demonstrate its working. You can tweak the code as you like.

Time complexity

The time complexity of this algorithm is ${O(n \times k \times log(k)).}$ Let’s break down why this is the case:

We get ${O(n)}$ by iterating each word present in the list of strings. ${n}$ is the length of the list.
Each word is sorted, and this step has a time complexity of ${O(k \times log(k)).}$ Here, k is the length of the longest string within the list.
The final step, in which we insert a key-value pair in the dictionary, is ${O(1).}$

Therefore, the overall time complexity becomes ${O(n \times k \times log(k)).}$

Space complexity

The space complexity of this algorithm is ${O(n)}$ . In the worst case, all the words would be unique and will not be anagrams of any other word. Thus, the size of the returned list of grouped anagrams would be ${n.}$

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments