Using Python, find anagrams for a list of words

Question

If I have a list of strings for example:

["car", "tree", "boy", "girl", "arc"...]

What should I do in order to find anagrams in that list? For example (car, arc). I tried using for loop for each string and I used if in order to ignore strings in different lengths but I can't get the right result.

How can I go over each letter in the string and compare it to others in the list in different order?

I have read several similar questions, but the answers were too advanced. I can't import anything and I can only use basic functions.

Answer 1

In order to do this for 2 strings you can do this:

def isAnagram(str1, str2):
    str1_list = list(str1)
    str1_list.sort()
    str2_list = list(str2)
    str2_list.sort()

    return (str1_list == str2_list)

As for the iteration on the list, it is pretty straight forward

Answer 2

Create a dictionary of (sorted word, list of word). All the words that are in the same list are anagrams of each other.

from collections import defaultdict

def load_words(filename='/usr/share/dict/american-english'):
    with open(filename) as f:
        for word in f:
            yield word.rstrip()

def get_anagrams(source):
    d = defaultdict(list)
    for word in source:
        key = "".join(sorted(word))
        d[key].append(word)
    return d

def print_anagrams(word_source):
    d = get_anagrams(word_source)
    for key, anagrams in d.iteritems():
        if len(anagrams) > 1:
            print(key, anagrams)

word_source = load_words()
print_anagrams(word_source)

Or:

word_source = ["car", "tree", "boy", "girl", "arc"]
print_anagrams(word_source)

Answer 3

One solution is to sort the word you're searching anagrams for (for example using sorted), sort the alternative and compare those.

So if you would be searching for anagrams of 'rac' in the list ['car', 'girl', 'tofu', 'rca'], your code could look like this:

word = sorted('rac')
alternatives = ['car', 'girl', 'tofu', 'rca']

for alt in alternatives:
    if word == sorted(alt):
        print alt

Answer 4

There are multiple solutions to this problem:

1. Classic approach

   First, let's consider what defines an anagram: two words are anagrams of each other if they consist of the same set of letters and each letter appears exactly the same number or time in both words. This is basically a histogram of letters count of each word. This is a perfect use case for collections.Counter data structure (see docs). The algorithms is as follows:

   • Build a dictionary where keys would be histograms and values would be lists of words that have this histogram.
   • For each word build it's histogram and add it to the list that corresponds to this histogram.
   • Output list of dictionary values.

   Here is the code:

   from collections import Counter, defaultdict
   
   def anagram(words):
       anagrams = defaultdict(list)
       for word in words:
           histogram = tuple(Counter(word).items()) # build a hashable histogram
           anagrams[histogram].append(word)
       return list(anagrams.values())
   
   keywords = ("hi", "hello", "bye", "helol", "abc", "cab", 
                   "bac", "silenced", "licensed", "declines")
   
   print(anagram(keywords))
   

   Note that constructing Counter is O(l), while sorting each word is O(n*log(l)) where l is the length of the word.

2. Solving anagrams using prime numbers

   This is a more advanced solution, that relies on the "multiplicative uniqueness" of prime numbers. You can refer to this SO post: Comparing anagrams using prime numbers, and here is a sample python implementation.

Answer 5

Sort each element then look for duplicates. There's a built-in function for sorting so you do not need to import anything

Answer 6

Since you can't import anything, here are two different approaches including the for loop you asked for.

Approach 1: For Loops and Inbuilt Sorted Function

word_list = ["percussion", "supersonic", "car", "tree", "boy", "girl", "arc"]

# initialize a list
anagram_list = []
for word_1 in word_list: 
    for word_2 in word_list: 
        if word_1 != word_2 and (sorted(word_1)==sorted(word_2)):
            anagram_list.append(word_1)
print(anagram_list)

Approach 2: Dictionaries

def freq(word):
    freq_dict = {}
    for char in word:
        freq_dict[char] = freq_dict.get(char, 0) + 1
    return freq_dict

# initialize a list
anagram_list = []
for word_1 in word_list: 
    for word_2 in word_list: 
        if word_1 != word_2 and (freq(word_1) == freq(word_2)):
            anagram_list.append(word_1)
print(anagram_list)

If you want these approaches explained in more detail, here is an article.

Answer 7

def findanagranfromlistofwords(li):
    dict = {}
    index=0
    for i in range(0,len(li)):
        originalfirst = li[index]
        sortedfirst = ''.join(sorted(str(li[index])))
        for j in range(index+1,len(li)):
            next = ''.join(sorted(str(li[j])))
            print next
            if sortedfirst == next:
                dict.update({originalfirst:li[j]})
                print "dict = ",dict
        index+=1

    print dict

findanagranfromlistofwords(["car", "tree", "boy", "girl", "arc"])

Answer 8

Most of previous answers are correct, here is another way to compare two strings. The main benefit of using this strategy versus sort is space/time complexity which is n log of n.

1.Check the length of string

2.Build frequency Dictionary and compare if they both match then we have successfully identified anagram words

def char_frequency(word):
    frequency  = {}
    for char in word:
        #if character  is in frequency then increment the value
        if char in frequency:
            frequency[char] += 1
        #else add character and set it to 1
        else:
            frequency[char] = 1
    return frequency 


a_word ='google'
b_word ='ooggle'
#check length of the words 
if (len(a_word) != len(b_word)):
   print ("not anagram")
else:
    #here we check the frequecy to see if we get the same
    if ( char_frequency(a_word) == char_frequency(b_word)):
        print("found anagram")
    else:
        print("no anagram")

Answer 9

def all_anagrams(words: [str]) -> [str]:
    word_dict = {}
    for word in words:
        sorted_word  = "".join(sorted(word))
        if sorted_word in word_dict:
            word_dict[sorted_word].append(word)
        else:
            word_dict[sorted_word] = [word]
    return list(word_dict.values())  

Answer 10

Solution in python can be as below:

class Word:
    def __init__(self, data, index):
        self.data = data
        self.index = index

def printAnagrams(arr):
    dupArray = []
    size = len(arr)

    for i in range(size):
        dupArray.append(Word(arr[i], i))

    for i in range(size):
        dupArray[i].data = ''.join(sorted(dupArray[i].data))

    dupArray = sorted(dupArray, key=lambda x: x.data)

    for i in range(size):
        print arr[dupArray[i].index]

def main():
    arr = ["dog", "act", "cat", "god", "tac"]

    printAnagrams(arr)

if __name__== '__main__':
    main()

1. First create a duplicate list of same words with indexes representing their position indexes.
2. Then sort the individual strings of the duplicate list
3. Then sort the duplicate list itself based on strings.
4. Finally print the original list with indexes used from duplicate array.

The time complexity of above is O(NMLogN + NMLogM) = O(NMlogN)

Answer 11

I'm using a dictionary to store each character of string one by one. Then iterate through second string and find the character in the dictionary, if it's present decrease the count of the corresponding key from dictionary.

class Anagram:

    dict = {}

    def __init__(self):
        Anagram.dict = {}

    def is_anagram(self,s1, s2):
        print '***** starting *****'

        print '***** convert input strings to lowercase'
        s1 = s1.lower()
        s2 = s2.lower()

        for i in s1:
           if i not in Anagram.dict:
              Anagram.dict[i] = 1
           else:
              Anagram.dict[i] += 1

        print Anagram.dict

        for i in s2:
           if i not in Anagram.dict:
              return false
           else:
              Anagram.dict[i] -= 1

        print Anagram.dict

       for i in Anagram.dict.keys():
          if Anagram.dict.get(i) == 0:
              del Anagram.dict[i]

       if len(Anagram.dict) == 0:
         print Anagram.dict
         return True
       else:
         return False

Answer 12

import collections

def find_anagrams(x):
    anagrams = [''.join(sorted(list(i))) for i in x]
    anagrams_counts = [item for item, count in collections.Counter(anagrams).items() if count > 1]
    return [i for i in x if ''.join(sorted(list(i))) in anagrams_counts]

Answer 13

Simple Solution in Python:

def anagram(s1,s2):

    # Remove spaces and lowercase letters
    s1 = s1.replace(' ','').lower()
    s2 = s2.replace(' ','').lower()

    # Return sorted match.
    return sorted(s1) == sorted(s2)

Answer 14

This one is gonna help you:

Assuming input is given as comma separated strings

console input: abc,bac,car,rac,pqr,acb,acr,abc

in_list = list()
in_list = map(str, raw_input("Enter strings seperated by comma").split(','))
list_anagram = list()

for i in range(0, len(in_list) - 1):
    if sorted(in_list[i]) not in list_anagram:
        for j in range(i + 1, len(in_list)):
            isanagram = (sorted(in_list[i]) == sorted(in_list[j]))
            if isanagram:
                list_anagram.append(sorted(in_list[i]))
                print in_list[i], 'isanagram'
                break

Answer 15

This works fine:

def find_ana(l):
    a=[]
    for i in range(len(l)):
        for j in range(len(l)): 
            if (l[i]!=l[j]) and (sorted(l[i])==sorted(l[j])):
                a.append(l[i])
                a.append(l[j])

    return list(set(a))

Answer 16

# list of words
words = ["ROOPA","TABU","OOPAR","BUTA","BUAT" , "PAROO","Soudipta",
        "Kheyali Park", "Tollygaunge", "AROOP","Love","AOORP",
         "Protijayi","Paikpara","dipSouta","Shyambazaar",
        "jayiProti", "North Calcutta", "Sovabazaar"]

#Method 1
A = [''.join(sorted(word)) for word in words]

dict ={}

for indexofsamewords,samewords in enumerate(A):
    dict.setdefault(samewords, []).append(indexofsamewords)
    
print(dict)
#{'AOOPR': [0, 2, 5, 9, 11], 'ABTU': [1, 3, 4], 'Sadioptu': [6, 14], ' KPaaehiklry': [7], 'Taeggllnouy': [8], 'Leov': [10], 'Paiijorty': [12, 16], 'Paaaikpr': [13], 'Saaaabhmryz': [15], ' CNaachlortttu': [17], 'Saaaaborvz': [18]}

for index in dict.values(): 
    print( [words[i] for i in index ] )
    

The Output :

['ROOPA', 'OOPAR', 'PAROO', 'AROOP', 'AOORP']
['TABU', 'BUTA', 'BUAT']
['Soudipta', 'dipSouta']
['Kheyali Park']
['Tollygaunge']
['Love']
['Protijayi', 'jayiProti']
['Paikpara']
['Shyambazaar']
['North Calcutta']
['Sovabazaar']

Answer 17

A set is an appropriate data structure for the output, since you presumably don't want redundancy in the output. A dictionary is ideal for looking up if a particular sequence of letters has been previously observed, and what word it originally came from. Taking advantage of the fact that we can add the same item to a set multiple times without expanding the set lets us get away with one for loop.

def return_anagrams(word_list):
    d = {}
    out = set()
    for word in word_list:
        s = ''.join(sorted(word))
        try:
            out.add(d[s])
            out.add(word)
        except:
            d[s] = word
    return out

A faster way of doing it takes advantage of the commutative property of addition:

import numpy as np

def vector_anagram(l):
    d, out = dict(), set()
    for word in l:
        s = np.zeros(26, dtype=int)
        for c in word:
            s[ord(c)-97] += 1
        s = tuple(s)
        try:
            out.add(d[s])
            out.add(word)
        except:
            d[s] = word
    return out

Answer 18

Simply use the Counter method available in Python3 collections package.

str1="abc"
str2="cab"

Counter(str1)==Counter(str2)
# returns True i.e both Strings are anagrams of each other.

Answer 19

NOTE: This is not a new solution but I have added comments and example to help someone understand logic when using dictionaries.

Find anagrams from a given list of strings
["dog", "god", "cat"]

1. Create a dictionary, where the key is a sorted str element of the given list and values are a list of corresponding anagrams present in the list

{dgo: ['dog', 'god'], act: ['cat'] }

2. Get the List of anagram

['dog', 'god'] 

def is_anagram(list_of_str):

    new_list = []
    empty_dict ={}
    
    for item in list_of_str:
        sorted_item = ''.join(sorted(item))
        if sorted_item not in empty_dict:
            empty_dict[sorted_item] = [item]
        else:
            empty_dict[sorted_item].append(item)
    # return empty_dict 
    for k,v in empty_dict.items():
        if len(v)>=2:
            new_list.append(v)
    return new_list

a = ['dog', 'god', 'cat']
print(is_anagram(a))