Algorithm For Finding Anagrams
Finding all the anagrams in a given list of strings.
What is an Anagram ?
An anagram is a string of letters formed by rearranging the letters of another string.
Note : The count of each letter in the newly formed string is same as the count of each letter in the original string.
Example : pat & apt are both anagrams of string tap
Finding Anagrams The idea behind finding all the anagrams in a given list is to create a hashmap. The key of the hashmap is the word formed with alphabets in the sorted order. All the values (words) corresponding to the given key will form the same key when sorted alphabetically.
Example: When the characters in word pat are sorted alphabetically, a word apt is formed. So is true for words tap and apt. Thus “apt” becomes the key in the hashmap representing the words apt, pat and tap that are anagrams.
Python : Finding Anagrams
#!/usr/bin/python3
anagram = {}
word_list = { "apt", "car", "pat", "dog", "tap", "god", "arc", "airmen", "marine", "remain" }
for word in word_list:
word = word.strip()
hashkey = "".join(sorted(word))
if hashkey not in anagram:
anagram[hashkey] = []
anagram[hashkey].append(word)
# print anagram
for val in anagram.items():
if(len(val) > 1):
print (val)
Output
('dgo', ['god', 'dog'])
('apt', ['tap', 'apt', 'pat'])
('acr', ['arc', 'car'])
('aeimnr', ['remain', 'marine', 'airmen'])