Problem Statement:

Group Anagrams- You have given a list of words. Write a program to returns a list of sets of anagrams.

Args:

• words – list of words to process

Example:

Input: ['cat', 'dog', 'god']
Output: [{'cat'}, {'dog', 'god'}]

Example:

Ignore the duplicate words in the input list.

Input= ['cat', 'dog', 'cat', 'god']
Output= [{'cat'}, {'dog', 'god'}]

The word cat occurs twice in the input list. The word cat occurs only once in the output list of sets.

This question was asked in Goldman Sachs Coderpad interview.

Explanation:

What is anagram?

The string is anagram if it is formed by changing the positions of the characters.

It means anagram strings will be having the same set of characters and the same length.

Example:

The string adcb is an anagram of string abdc.

How to verify if the two strings are anagram?

• Sort the characters in both given strings.
• After sorting, if two strings are similar, they are an anagram of each other.

Python Program (Group Anagram):

[python]
def getAnagramSet(words):

#remove duplicate words from the list
words=list(set(words))

#find the anagram of each word in the list
anagramWords=[”.join(sorted(x)) for x in words]

finalOut=[]
for word in set(anagramWords):
#find the index for all occurences of string word
ind=[i for i, x in enumerate(anagramWords) if x==word]

#make the list of all the string
#which is anagram to each other
tempOut=[]
for i in ind:
tempOut.append(words[i])

#append all the set to the final output list
finalOut.append(set(tempOut))

return finalOut

words=[‘cat’, ‘dog’, ‘god’, ‘cat’]

if __name__ == "__main__":
print(getAnagramSet(words))
[/python]

Output:

[{'god', 'dog'}, {'cat'}]

Some important methods used to solve this programming challenge:

• sorted() builtin function to sort the characters in the string (difference between sort() and sorted())
• list comprehension technique to create the list

Kindly share if you find any other optimized method to solve this group anagram problem. Also if you can write this program in any other programming languages like C/C++ or Java, write in the comment.

Happy Programming!