DEV Community

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...

Read full post

Jason C. McDonald • Aug 9 '19 • 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))

O(n), if you're wondering.

Aadi Bajpai • Aug 11 '19

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

Jason C. McDonald • Aug 11 '19 • 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.

Jason C. McDonald • Aug 11 '19 • 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.

Aadi Bajpai • Aug 11 '19

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').

Jason C. McDonald • Aug 11 '19

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

Caleb Adepitan • Aug 9 '19 • 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"))

Ben Sinclair • Aug 10 '19

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

Caleb Adepitan • Aug 10 '19 • 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.

Ben Sinclair • Aug 10 '19

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.

Caleb Adepitan • Aug 10 '19

digitalfortress.tech/js/exclamatio...

Alex Lohr • Aug 12 '19

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

anagrams('abc', 'aad') // => true

Sem Limi • Jul 15 '20 • 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;
  }

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

console.log(anagrams("anagram", "nagarams")); // false

Alex Lohr • Aug 12 '19

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);
}

Frederik 👨‍💻➡️🌐 Creemers • Oct 2 '19

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

Paweł Kowalski • Aug 10 '19

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 :)

Adams Stark • Mar 14 '21

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, "");
...

 ###

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

Developeranees • May 5 '22

This code block is no longer available. The original code is shown below.


    
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');