DEV Community

Cover image for Anagrams Checker - Three JavaScript Solutions

Anagrams Checker - Three JavaScript Solutions

Sarah Chima on August 09, 2019

I started a series on JavaScript solutions to common algorithms and javascript problems. In case you missed the first one, here's a link to it. Ear...
Collapse
 
codemouse92 profile image
Jason C. McDonald • Edited

It's Python (so, off-topic), but I couldn't help myself:

def anagram_checker(word1, word2):
    word1 = [c for c in word1.lower() if c.isalpha()]
    word2 = [c for c in word2.lower() if c.isalpha()]
    return (len(word1) == len(word2) and set(word1) == set(word2))
Enter fullscreen mode Exit fullscreen mode

O(n), if you're wondering.

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.

Collapse
 
calebpitan profile image
Caleb Adepitan • Edited

What do you think?

function anagrams(a, b) {
  let i = 0
  let sumA = 0
  let sumB = 0
  a = a.replace(/[\W]/g, "").toLowerCase()
  b = b.replace(/[\W]/g, "").toLowerCase()
  if (a.length !== b.length) return false
  !(function sumCharCode() {
    if (i < a.length) {
      sumA += a.charCodeAt(i)
      sumB += b.charCodeAt(i)
      i++
      sumCharCode()
    }
  })()
  return sumA === sumB;
}

console.log(anagrams("listen", "silent"))

Enter fullscreen mode Exit fullscreen mode

Copyright (c) 2019 Caleb Pitan
😇😁😁

Collapse
 
moopet profile image
Ben Sinclair

I think that function expressions using ! are there just to make the code less readable.

Collapse
 
calebpitan profile image
Caleb Adepitan • Edited

My bad! I won't lie to you I really don't know the use of the "!", but I think it's to indicate an iife inside the function, hence aid readability. I put it because in my early years I saw a lot of these around, and I thought having it around or not affects nothing. Didn't know it affects readability, although I don't understand how. I wouldn't mind if you told me.

Thread Thread
 
moopet profile image
Ben Sinclair

I prefer explicit to implicit (comes from enjoying Python too much...) and !(function(){...}(); is just... well, if you haven't seen it before you have no idea what the gosh darnit is going on.

Thread Thread
 
calebpitan profile image
Caleb Adepitan
Collapse
 
lexlohr profile image
Alex Lohr

I initially thought about that approach, but discarded it for an obvious reason:

anagrams('abc', 'aad') // => true
Enter fullscreen mode Exit fullscreen mode
Collapse
 
calebpitan profile image
Caleb Adepitan

Smart 😃.
It's just too obvious. Didn't take time to analyze it. It struck my mind as I saw this post and I put it down.

Collapse
 
joeberetta profile image
Joe Beretta

I thought about using \W instead of ^w as you wrote)

Collapse
 
calebpitan profile image
Caleb Adepitan

There's really no difference, it's just left to choice.

Thread Thread
 
joeberetta profile image
Joe Beretta

Know it. But I think this way is more elegant and perfomance

Collapse
 
sem8 profile image
Sem Limi • Edited

Solution 1 might not be completely correct if you don't check that the length of s and t are the same otherwise return false like so:

 if (s.length !== t.length) {
    return false;
  }
Enter fullscreen mode Exit fullscreen mode

Otherwise this test will return true even though it should be false

console.log(anagrams("anagram", "nagarams")); // false
Enter fullscreen mode Exit fullscreen mode
Collapse
 
lexlohr profile image
Alex Lohr

My first solution (ES2019) looks like this:

const isAnagram = (word1, word2) => {
    const charsInWord = {};
    const maxLength = Math.max(word1.length, word2.length);
    for (let index = 0; index < maxLength; index++) {
        const char1 = word1.charCodeAt(index);
        const char2 = word2.charCodeAt(index);
        if (char1 >= 97 && char1 <= 122) {
            charsInWord[char1] = (charsInWord[char1] || 0) + 1;
        }
        if (char2 >= 97 && char2 <= 122) {
            charsInWord[char2] = (charsInWord[char2] || 0) - 1;
        }
    }
    return (Object.values(charsInWord) || { a: 0 }).every((charCount) => charCount === 0);
}
Collapse
 
_bigblind profile image
Frederik 👨‍💻➡️🌐 Creemers

Here's an O(∞) solution inspired by bogosort. If it halts, a and b are anagrams.

def anagrams(a, b):
    while True:
        b = str(random.shuffle(b))
        if a == b:
            return True
Enter fullscreen mode Exit fullscreen mode
Collapse
 
pavelloz profile image
Paweł Kowalski

My intuition, before i saw any of the solutions, went into the 2nd one because it feels like it would be the easiest to understand and the fastest. I wonder if thats the case ;)
Thank you for the brain teaser, good beginning of the day :)

Collapse
 
adamsstark profile image
Adams Stark

In order to remove spaces, you are calling string.replace once for every occurrence of " " (space) in each string. An easier way to remove whitespace in a string is to use a regular expression object with a global modifier, which will replace all matching characters in the string. Then, you can get rid of your while-loops, and your code becomes slightly easier to read. I hope it will help you to complete your Anagram checker project .

  ## function findAnagram (firstWord, secondWord) {
// "/ /g" is a regular expression object that finds all spaces in a string.
secondWord = secondWord.replace(/ /g, "");
firstWord = firstWord.replace(/ /g, "");
...

 ###
Enter fullscreen mode Exit fullscreen mode

You can also use the /\s/g regular expression object to replace all whitespace including tabs, newlines, etc.

Collapse
 
developeranees profile image
Developeranees
const same = (s1, s2) => { const str1 = s1.toLowerCase(); const str2 = s2.toLowerCase(); if (str1 === str2) return true; if (str1.length !== str2.length) return false; const obj1 = {}; const obj2 = {}; str1.split('').forEach((s, i) => { obj1[str1[i]] = (obj1[str1[i]] || 0) + 1; obj2[str2[i]] = (obj2[str2[i]] || 0) + 1; }); const arr1 = Object.entries(obj1).map(String).sort().toString(); const arr2 = Object.entries(obj2).map(String).sort().toString(); return arr1 === arr2; }; same('textwisttime', 'timewisttext');
Collapse
 
rajaosama profile image
Raja Osama • Edited

tried all the above and the below solutions but the least execution time was taken by this one.

Collapse
 
lauragift21 profile image
Gift Egwuenu

Great article Sarah! Mind sharing any resources for leveling up on Data Structures and Algorithms. Thanks

Collapse
 
sarah_chima profile image
Sarah Chima

I'm taking a course by Stephen Grider on Udemy. Another recommended course is by Colt Steele - JavaScript Algorithms and Data Structures Masterclass.

Collapse
 
joeattardi profile image
Joe Attardi

This is a favorite interview question of mine. The character map solution is what most people seem to do - myself included!

Collapse
 
shivraj97 profile image
Shivraj97

Solution 2 is not correct. What if I pass a word with extra letters to string 2???

Collapse
 
alexpanchuk profile image
Alex Panchuk

For example?