Wajahat 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):
# write your code here
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]):
ret.add(i)
ret.add(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.

wim wim
Answer

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]
Comments