Wajahat - 2 months ago 6
Python Question

# 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
``````

Update: Just to add, not looking for built-in pythonic solutions such as using
`Counter`
which are already optimized. Have added Mike's suggestions, but still exceeding time-limit.

Your solution is slow because you're not taking advantage of python's data structures.

Here's a solution that collects results in a dict:

``````class Solution:
def anagrams(self, strs):
d = {}
for word in strs:
key = tuple(sorted(word))
try:
d[key].append(word)
except KeyError:
d[key] = [word]
return [w for ws in d.values() for w in ws if len(ws) > 1]
``````
Source (Stackoverflow)