# Find group of strings that are anagrams

This question refers to this problem on lintcode. I have a working solution, but it takes too long for the huge testcase. I am wondering how can it be improved? Maybe I can decrease the number of comparisons I make in the outer loop.

class Solution:
# @param strs: A list of strings
# @return: A list of strings
def anagrams(self, strs):
ret=set()
for i in range(0,len(strs)):
for j in range(i+1,len(strs)):
if i in ret and j in ret:
continue
if Solution.isanagram(strs[i],strs[j]):

return [strs[i] for i in list(ret)]

@staticmethod
def isanagram(s, t):
if len(s)!=len(t):
return False
chars={}
for i in s:
if i in chars:
chars[i]+=1
else:
chars[i]=1

for i in t:
if i not in chars:
return False
else:
chars[i]-=1
if chars[i]<0:
return False

for i in chars:
if chars[i]!=0:
return False
return True


Different algorithm

Instead of considering all pairs of strings which leads to a O(n^2) behavior (where n is the number of strings), you could operate differently and use a dictionnary to group words based on some kind of signature with would be the same for anagrams and different for non-anagrams.

In your case, you could use the "sorted" version of a word as a signature : only 2 anagrams will be indentical once sorted. Once you've determined how to compute this, you can easily define a dictionnary mapping sorted words to the anagrams they correspond to.

This is a typical situation where the setdefault method is useful.

You can write something like:

t1 = ["lint", "intl", "inlt", "code"] # return ["lint", "inlt", "intl"].
t2 = ["ab", "ba", "cd", "dc", "e"] # return ["ab", "ba", "cd", "dc"].

def anagrams(word_list):
anagrams = {}
for w in word_list:
anagrams.setdefault(''.join(sorted(w)), []).append(w)
# print(anagrams)
return sorted(  # sort is to make results always the same
[w for anagrams in anagrams.values()
if len(anagrams) > 1
for w in anagrams])

assert anagrams(t1) == ['inlt', 'intl', 'lint']
assert anagrams(t2) == ['ab', 'ba', 'cd', 'dc']

• I think that it is also a good idea to discuss how to define a key for a group of anagrams. The naive solution is to sort the string, a group of anagrams should be sorted to the same string, but sorting is not efficient, not taking advantage of alphabetic number is size of 26, constant size. – Jianmin Chen Feb 4 '17 at 23:50

There seems to be no need for a class here, since you don't use any class features, really. But if it is part of the defined interface of lintcode, so be it...

The test for an anagram can be easiest achieved using collections.Counter:

from collections import Counter

def is_anagram(str1, str2):
return Counter(str1) == Counter(str2)


Counter will create a (Ordered) dict containing counts of different objects in the iterable input. So for the example of a string it will create a dictionary, just like you are building for s. Then it is just a matter of checking whether they are the same for str1 and str2.

You can add some optimization by first checking the lengths and using the short-circiut notation of pythons and if you want/need to:

def is_anagram(str1, str2):
return len(str1) == len(str2) and Counter(str1) == Counter(str2)


Your other code can also be simplified a bit. In python it is recommended to iterate over the object itself, not its indices and use enumerate if you do need the index:

class Solution:
# @param strs: A list of strings
# @return: A list of strings
def anagrams(self, strings):
anagrams = set()
for i, str1 in enumerate(strings):
if str1 in anagrams:
continue
for str2 in strings[i+1:]:
if str2 in anagrams:
continue
if is_anagram(str1, str2):

return [string for string in strings if string in anagrams]


I also modified the continue to trigger more often, chose more descriptive variable names and added some whitespace after parameters in a list (is_anagram(str1, str2)).

EDIT: After actually trying the challenge myself and running into time-limit exceeded also with the above code I came up with this algorithm:

from collections import Counter

def is_anagram(str1, str2):
return len(str1) == len(str2) and Counter(str1) == Counter(str2)

class Solution:
# @param strs: A list of strings
# @return: A list of strings
def anagrams(self, strings):
counts = Counter("".join(sorted(word)) for word in strings)
out = []
for word in strings:
word_sorted = "".join(sorted(word))
if counts[word_sorted] > 1:
out.append(word)
return out


This first builds a Counter to see how often each sorted version of all words comes up. It then build up a list with all words where the sorted word appears at least twice. This runs in ~460 ms on the largest test case (opposed to about 4800ms for the code above).

• @Wajahat Have a look at my updated answer for some more suggestions. – Graipher Sep 9 '16 at 8:47
• I worked on the similar question today, the basic idea I took is to design a hash function, and hashed function time complexity is O(n) using counting sort instead of comparison-based sort O(nlogn). code review is codereview.stackexchange.com/a/154458/123986 – Jianmin Chen Feb 4 '17 at 23:46