JS Anagrams with Big O Notation

#javascript #tutorial #algorithms #programming

We say that two strings are anagrams of each other if they have the exact same letters in same quantity of existance of each letter, regardless of non-alphabetic letters and case sensitivity.

Here's an example

// 'hello', 'elloh' -> anagrams
// 'love', 'hate' -> not anagrams
// 'i'm 26 years old' -> 'myeald oirs o' -> anagrams

Well, the Solution is Simple

We just need to remove all non-alphabetic letters first, and turn all letters into lower case.

// 'Hello World!@# ---30..' -> 'helloworld30'

const inputString = 'Hello World!@# ---30..'
inputString.toLowerCase().replace(/[\W_]+/g, ''); // returns 'helloworld30'

\W leaves the underscore, A short equivalent for [^a-zA-Z0-9] would be [\W_]

Then we need to convert string to array, sort the array alphabetically, and then turn it back into a string

// 'hello' -> ['h', 'e', 'l', 'l', 'o'] -> ['e', 'h', 'l', 'l', 'o'] -> ehllo

const inputString = 'Hello World!@# ---30..'
inputString.toLowerCase().replace(/[\W_]+/g, '').split('').sort().join(''); // returns '03dehllloorw'

Here's the final code

const anagrams = (firstInput, secondInput) => {
  return (
    firstInput
      .toLowerCase()
      .replace(/[\W_]+/g, '')
      .split('')
      .sort()
      .join('') ===
    secondInput
      .toLowerCase()
      .replace(/[\W_]+/g, '')
      .split('')
      .sort()
      .join('')
  );
}

Big O Notation
Time Complexity: O(n * Log n) because we've used sort algorithm

However, a Better solutions do exist, We'll also write another solution

const anagrams = (firstInput, secondInput) => {
  firstInput = firstInput.toLowerCase().replace(/[\W_]+/g, '');
  secondInput = secondInput.toLowerCase().replace(/[\W_]+/g, '');

  if (firstInput.length !== secondInput.length) {
    return false;
  }

  const inputLetterCount = {};

  for (let i = 0; i < firstInput.length; i++) {
    const currentLetter = firstInput[i];
    inputLetterCount[currentLetter] = inputLetterCount[currentLetter] + 1 || 1;
  }

  for (let i = 0; i < secondInput.length; i++) {
    const currentLetter = secondInput[i];
    if (!inputLetterCount[currentLetter]) return false;
    else inputLetterCount[currentLetter]--;
  }

  return true;
};