Wajahat - 1 year ago 54

Python Question

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

`Counter`

Answer Source

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