Group Anagrams- You have given a list of words. Write a program to returns a list of sets of anagrams.
Args:
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.
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?
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))
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())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!
I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.