Checking if two strings are anagrams in Python

Question

The code written in Python 3.6 mostly using Python's built in functions sorted and len. First I'm checking for the edge case that the two given strings are not of the same length obviously. Then I'm sorting the strings and comparing if their sorted value are equal to each other with a boolean expression. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

• Just for the sake of practising Big-O this function runs in \$O(1)\$ constant complexity time because regardless of the strings given the function will always return a Boolean value. Is this correct? I realized my assumption was not correct since the function will run in the time complexity of the sorted built-in function which is \$nlog(n)\$.

• If you were an interviewer would you prefer the candidate to not use Python's built in functions and to resort to a more manual way of solving the problem?

def is_anagram(string1, string2):


    while len(string1) == len(string2):

    # Testing sorted values equality 
        if sorted(string1) == sorted(string2):
            return True
        return False

    return 'The strings are not anagrams they have differing lengths'


print(is_anagram('cat', 'cra'))

Answer 1

1. You can change your if to just be return.
2. You should change your while to an if, as it makes no sense for it to be while.
3. You shouldn't return a string on invalid input, instead you could raise a ValueError.

This can get:

def is_anagram(string1, string2):
    if len(string1) == len(string2):
        return sorted(string1) == sorted(string2)
    raise ValueError('The strings are not anagrams they have differing lengths')

However I wouldn't raise, and so you can just use:

def is_anagram(string1, string2):
    return sorted(string1) == sorted(string2)

---

To answer your questions:

• The \$O\$ complexity for your function is not \$O(1)\$. Lets take the different aspects of your function:

  • len(n) is \$O(1)\$
  • int == int is \$O(1)\$
  • sorted(n) is \$n\log{n}\$
  • str == str is \$O(n)\$
  • len(a) == len(b) is \$O(1)\$
  • sorted(a) == sorted(b) is \$O(\min(a, b) + a\log{a} + b\log{b})\$

  Since the function will short circuit if len(a) == len(b) we know that \$a = b = n\$. And so the complexity becomes \$O(n + n\log{n})\$. This may be ok to simplify to \$O(n\log{n})\$, as \$O(n + n\log{n}) = O(n(1 + \log{n}))\$

  You can however use collections.Counter to reduce your sorted complexity to \$O(n)\$. And so keeping the short circuiting your function would be \$O(n)\$, otherwise it would be \$O(a + b)\$. And so to use this you can use:

  from collections import Counter
  
  
  def is_anagram(string1, string2):
      return Counter(string1) == Counter(string2)
  

• I would prefer you use the builtin functions, as it should lead to less code to maintain.

Answer 2

Nice to see someone even think about efficiency. So many coders (especially young/new ones) just write things the simple way. Comparing the sort strings is simple. It's not necessarily efficient.

As an interviewer I would be happy to see you use built-in functions. There is no point in re-inventing the wheel. But you have to use the right functions at the right time.

As an interviewer, the first question I want you to ask before you optimize is about the problem space. What lengths of strings are you likely to be comparing? If the answer is 10 then it isn't worth optimizing. If the answer is 2048 then you'll want to think about it.

"Premature optimization is the root of all evil [...] in programming" - Donald Knuth¹

A second question about the problem space is "how often will this program be used and in what context?" If you are writing a one-time use program then just do it the faster simplest way you can think of. There is little point in expending brain cells on optimizing something that will barely be used. If the answer is that this will be a frequently used component in a life support system then you darn well better plan to optimize, and get it right.

Test your resulting program. In an interview I would want you to at least describe some sample strings for comparison. What's the worst case pair of strings? (I think it's a pair that are different by one character and the two characters are the ones that would be last in the sorted string within your element space. That is, if you are comparing lower case letters the difference is a "y" in one string instead of a "z" in the other.) In real world test your "optimized" program against the simple one to see how they compare on time use. Some results are bound to surprise you. There are lots of factors that will surprise you about implementation details.

¹_{https://en.wikiquote.org/wiki/Donald_Knuth#Computer_Programming_as_an_Art_(1974)}

Answer 3

while len(string1) == len(string2):

Why are you using while here instead of if?

I think it's "ugly" to have a function that has mixed return types, in your case booleans or a string.

You don't need to test the length before you check if the sorted lists are the same.

Big-o of this would be the Big-o of whatever sorting function sorted are using, I think it is timsort in python so the big-o would be \$n \log n\$.

If they are asking for a python dev it's good to use builltins because that shows you know the language.

Instead of useing an if, you could just return the value of the boolean operation. I would probably implement it something like this.

def is_anagram(s1,s2):
    return sorted(s1) == sorted(s2)

Answer 4

I personally would not be thrilled with that response in an interview. I mean, it's perfectly effective for exact matching, but some assumptions were made here.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once

The definition explicitly states that it matches all the original letters exactly once. Not all characters are letters, however. Within the function, a match is made by sorting the strings and seeing if they are equal. The assumptions that are not great are that each letter will have the same capitalisation, and that whitespace or even punctuation matters. This may indeed be the case, but it is not explicitly stated in the definiton.

Anagrams that will fail:
"funeral" "real fun"
"Madam Curie" "Radium came"
"election results" "Lies. Let's recount"

I would prefer something like the following. I am also making some assumptions here about whether the characters will match in isalpha without checking if that is actually the case in certain character sets. But hey, I speak English so that's all I personally care about until a customer complains about a bug about my code not working in their language, right?

def is_anagram(string1, string2):
  x={}
  for c in string1.lower():
    if c.isalpha():
      try:
        x[c]+=1
      except:
        x[c]=1
  for c in string2.lower():
    if c.isalpha():
      try:
        x[c]-=1
      except:
        return False
  for i in x.values():
    if i != 0:
      return False
  return True

As @graipher pointed out, this can be done in a pythonier way with the following:

Counter(filter(str.isalpha, map(str.lower, s1))) == Counter(filter(str.isalpha, map(str.lower, s2)))

Still learning python, so that's my lesson on collections.Counter.

And in action:

user@computer: ~$ python3.5 anagram2.py "cat" "tra"
False
user@computer: ~$ python3.5 anagram2.py "cat" "tac"
True
user@computer: ~$ python3.5 anagram2.py "funeral" "real fun"
True
user@computer: ~$ python3.5 anagram2.py "Madam Curie" "Radium came"
True
user@computer: ~$ python3.5 anagram2.py "Election results" "Lies.  Let's recount"
True