Find a group of strings that are anagrams

Question

This question relates to this issue on the linkcode . I have a working solution, but a huge test takes too much time. I am wondering how this can be improved? Perhaps I can reduce the number of comparisons that 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 add, don't look for built-in pythonic solutions, such as usage Counter, that are already optimized. They added Mike's proposals, but still exceeded the time limit.

Answer 1

Your solution is slow because you are not using python data structures.

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

Answer 2

, . .

# @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 both anagrams exist in set, there is no need to compare them.
            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)]

. , , . , chars -1 t, false. chars.

@staticmethod
def isanagram(s, t):
    # Test strings are the same length
    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 this is below 0, return false
            if chars[i] < 0:
                return False

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

Answer 3

, , ( collections.defaultdict), , . , collections.Counter. dict. , , , .

strings = ["cat", "act", "rat", "hut", "tar", "tact"]
anagrams = defaultdict(list)

for s in strings:
    anagrams[frozenset(Counter(s).items())].append(s)

print([v for v in anagrams.values()])
# [['hut'], ['rat', 'tar'], ['cat', 'act'], ['tact']]
print([x for v in anagrams.values() if len(v) > 1 for x in v])
# ['cat', 'act', 'rat', 'tar']

Of course, if you prefer not to use the built-in functionality, you can use only a few lines, and also use the usual dictinstead defaultdictand write your own Counter, similar to what you have your method isanagram, just without part of the comparison.

Answer 4

As a complement to @Mike's great answer, here is a good Pythonic way to do this:

import collections


class Solution:
    # @param strs: A list of strings
    # @return: A list of strings
    def anagrams(self, strs):
        patterns = Solution.find_anagram_words(strs)
        return [word for word in strs if ''.join(sorted(word)) in patterns]

    @staticmethod
    def find_anagram_words(strs):
        anagrams = collections.Counter(''.join(sorted(word)) for word in strs)
        return {word for word, times in anagrams.items() if times > 1}

Answer 5

Why not this?

str1 = "cafe"
str2 = "face"
def isanagram(s1,s2):
    return all(sorted(list(str1)) == sorted(list(str2)))

if isanagram(str1, str2):
    print "Woo"