Checking if two strings are anagrams in Python 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'))
You can change your if to just be return.
You should change your while to an if, as it makes no sense for it to be while.
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.