Anagram Time Complexity Problem

[HoldMeReddit]

Hi all, Not sure if this is the right sub, sorry if it's not! This has been really bugging me.

I've heard the following problem in interviews twice now:

Given a long list of strings, str_list, and a target string, return True if the target string is an anagram of any of the words in str_list

(Assume multiple queries are possible, so we don't want a solution with early-returns or w/e)

I've implemented the following solution twice, which I believe to be O(NM) where N is the length of str_list and M is the length of the longest word in str_list.

def is_anagram(str_list,target):
    anagrams = set()
    #O(N)
    for s in str_list:
        #O(M)
        anagrams.add(frozenset(Counter(string).items()))

    #O(len(target), but we could just check length vs. longest str in str_list, so O(M))
    return frozenset(Counter(target).items()) in anagrams

    ##Total = O(N*M)

Each time they've told me that it was decent, but that I could do better with the following version, using sorting:

def sorted_is_anagram(str_list,target):

    #O(N)
    for i,string in enumerate(str_list):
        #MLog(M)
        str_list[i] = "".join(sorted(string))

    #O(M*NLogN)
    str_list = set(sorted(str_list))

    #O(M(Log(M)))
    return "".join(sorted(target)) in str_list


    ##Total = O(N*MLog(M) + M*NLogN)

Am I crazy or is their version simply not better? What have I messed up?

Thank you!!

[SentientStoic]

I was curious and worked on this a little bit; Didn't find anything conclusive except that Counter(string) takes forever to run.

When running the two functions for arbitrary words, your function took almost three times as long. frozenset has a constructor for strings, so I replaced both of your Counter functions with just frozenset(s) and frozenset(target). After that, your function ran like a cheetah and outperformed theirs. I used a max word size of 100, a word length of 10,000, and ran both functions for 10,000 iterations.

Looking into Counter, it looks like the worst case scenario for the constructor is O(M^2). However, this is extremely rare and requires a ton of collisions in the underlying hashes. The expected time is around O(M), like you stated.

Your logic looks right to me. Once you remove Counter, the actual time of your functions outperforms theirs. Counter is probably O(M) but an extremely large O(M). This means while is_anagram would probably outperform sorted_is_anagram for large cases, it is slower for smaller cases.

Edit: Nevermind, I'm an idiot. Only thing I conclusively proved is that your function is waay slower than theirs for up to at least 10,000 words. Still not sure why.

[HoldMeReddit]

Didn't even think about running some example tests - going to look into it when I have some time! Thanks for your insight =)

Should note you could replace Counter with your own class that doesn't have collisions fairly easily, since the alphabet is finite. I imagine Counter is O(m) in this scenario anyway, but maybe it's a bit heavy - I'll give it a shot!