1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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']
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Jianmin Chen Feb 4 '17 at 23:50
0
\$\begingroup\$

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):
        # write your code here
        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):
                    anagrams.add(str1)
                    anagrams.add(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).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @Wajahat Have a look at my updated answer for some more suggestions. \$\endgroup\$ – Graipher Sep 9 '16 at 8:47
  • \$\begingroup\$ 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 \$\endgroup\$ – Jianmin Chen Feb 4 '17 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.