DEV Community

Discussion on: Anagrams Checker - Three JavaScript Solutions

Collapse
 
aadibajpai profile image
Aadi Bajpai

Flawed, would fail for strings like ('aabb', 'aaab')

Collapse
 
codemouse92 profile image
Jason C. McDonald • Edited

Good catch. I'd overlooked that edge case. Let me ponder....

AHA! The most obvious solution is...

def anagram_checker(word1, word2):
    word1 = sorted([c for c in word1.lower() if c.isalpha()])
    word2 = sorted([c for c in word2.lower() if c.isalpha()])
    return word1 == word2

sorted() employs Timsort, which has a worst case of O(n log n). Everything else is still only O(n).

Naturally, I'm sure there's a more efficient solution if I chew on this longer, but that'd be the one I'd probably use in production; reasonable performance, readable, maintainable, etc.

Thread Thread
 
codemouse92 profile image
Jason C. McDonald • Edited

EVEN BETTER! I just thought of a completely O(n) solution that relies on the commutative property of addition, and the fact that any letter would have a unique numeric equivalent (retrieved via ord()).

def anagram_checker(word1, word2):
    val1 = sum([ord(c) for c in word1.lower() if c.isalpha()])
    val2 = sum([ord(c) for c in word2.lower() if c.isalpha()])
    return val1 == val2

Ahhh, I love a good hack.

Thread Thread
 
aadibajpai profile image
Aadi Bajpai

Nope, this is flawed too. There are multiple ways to express a sum. 3+2=5 and 4+1=5 as well.

So ord('a') + ord('z') = ord('b') + ord('y')

Would fail for strings such as ('az', 'by').

Thread Thread
 
codemouse92 profile image
Jason C. McDonald

Hmm, hadn't considered that angle....

Thread Thread
 
evanoman profile image
Evan Oman

Prime factorizations are unique so if you map each letter to a prime and then take the product of those primes, you'd have a unique representation of the characters in the word. See this classic tweet for a better explanation.

Thread Thread
 
aadibajpai profile image
Aadi Bajpai

Not very efficient or fast, however.

Thread Thread
 
evanoman profile image
Evan Oman

I mean its time complexity is O(n)-ish but yeah the large number multiplication would get you for longer words.

Thread Thread
 
aadibajpai profile image
Aadi Bajpai

26th prime is 101 so I imagine zzzzzzzzzzzzz et all would take more time

Thread Thread
 
codemouse92 profile image
Jason C. McDonald • Edited

It's not efficient, but I wonder if a Cantor pairing of the ord() values would work. It would certainly be optimal if all the strings were two letters. The trouble is, those numbers get very big, very fast.