0
\$\begingroup\$

What is the time/space complexity of this algorithm which checks if two strings are anagrams? My guess is that time is \$O(n)\$ and space \$O(1)\$ but I am not sure. Can it be improved?

def anagram(str1, str2):
    s1 = list(str1)
    s2 = list(str2)
    freq1 = {}
    freq2 = {}

    for pos in s1:
        freq1[pos] = s1.count(pos)
    for pos in s2:
        freq2[pos] = s2.count(pos)
    if freq1 == freq2:
        return True
    else:
        return False
\$\endgroup\$
  • \$\begingroup\$ If n is the number of letters in your strings, you're going to have an amount of keys in your hash which is the same as the amount of letters, so space is also \$O(n)\$ \$\endgroup\$ – ChatterOne May 24 '17 at 8:10
  • \$\begingroup\$ A sorted list would be equal for both. \$\endgroup\$ – hjpotter92 May 24 '17 at 16:32
3
\$\begingroup\$

You take a string, and instantly make a list from it, and so space is at least \$O(n)\$. s1.count(pos) is an \$O(n)\$ operation, and is in a loop that loops \$n\$ times, and so the loop is \$O(n^2)\$. To make the loops \$O(n)\$ you just need to add 1 to the amount, and use a defaultdict to default everything to 0.

from collections import defaultdict

def anagram(str1, str2):
    freq1 = defaultdict(int)
    freq2 = defaultdict(int)

    for char in str1:
        freq1[char] += 1
    for char in str2:
        freq2[char] += 1

    return freq1 == freq2

This can however be simplified to use collections.Counter. And so you can use:

from collections import Counter

def anagram(str1, str2):
    return Counter(str1) == Counter(str2)

And so both the above have \$O(n)\$ time and space complexity.

\$\endgroup\$
  • \$\begingroup\$ The \$\Omega(n^2)\$ behaviour can't arise in this case (at least not in CPython), because all characters have distinct hashes. \$\endgroup\$ – Gareth Rees May 24 '17 at 18:48
  • \$\begingroup\$ @GarethRees My bad, I didn't know. Also, do you know of a source stating that, that I could learn from? \$\endgroup\$ – Peilonrayz May 24 '17 at 19:05
  • \$\begingroup\$ It's not documented anywhere, but it's a natural consequence of the implementation — see _Py_HashBytes. That's why I wrote "(at least not in CPython)" — another Python implementation might implement hashes differently and then it might not be true. \$\endgroup\$ – Gareth Rees May 24 '17 at 19:25
  • \$\begingroup\$ @GarethRees Thank you for the link, I'll have to look into that, :) \$\endgroup\$ – Peilonrayz May 24 '17 at 19:28
  • \$\begingroup\$ First time I saw Counter used. Cool! \$\endgroup\$ – user1685095 May 24 '17 at 20:12

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.