CODEWITHSUNDEEP
javascripttime-complexityanagram
mph85
mph85

Reputation: 1356

Javascript - Better solution for finding anagrams - Time complexity O (n log n)

DISCLAIMER

Hey everyone, I understand that there are few Javascript questions/answers that deal with figuring out the how to find if two words are anagrams.

I'm not just looking for a function that figures out whether two words/strings are anagrams. I'm looking for a function that will be quicker than the one provided below. Currently, I believe the time complexity of the function below is O (n log n).

I'd like to figure out a function that has a time complexity of O(n) or something that has a runtime that is quicker than the one provided.

CODE

const isAnagram = (str1, str2) => {

  str1 = str1.toLowerCase();
  str2 = str2.toLowerCase();


  if (str1.length !== str2.length) {
     return false
  }

  let sortStr1 = str1.split('').sort().join('').trim();
  let sortStr2 = str2.split('').sort().join('').trim();

  return sortStr1 === sortStr2
 };

console.log(isAnagram('dog', 'goD')); //true

Upvotes: 1

Views: 905

Answers (2)

Shidersz
Shidersz

Reputation: 17190

Here is another possible idea that comes from: An Algorithm for Finding Anagrams and is based on the fundamental theorem of arithmetic that states:

Every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors.

So, if we assign each letter in the alphabet to a prime number, and then compute the product of these numbers, this number will be unique ( because of the fundamental theorem of arithmetic). That means that for a multiset of letters, the product of prime numbers for each letter in that multiset is unique. Then, if two words or sentences have the same number, these two words or sentences are anagrams of each other.

Implementation:

let letters = {"a":2, "b":3, "c":5, "d":7, "e":11, "f":13, "g":17, "h":19, "i":23, "j":29, "k":31, "l":37, "m":41, "n":43, "o":47, "p":53, "q":59, "r":61, "s":67, "t":71, "u":73, "v":79, "w":83, "x":89, "y":97, "z":101};

const isAnagram = (str1, str2) =>
{
    str1 = str1.toLowerCase();
    str2 = str2.toLowerCase();            
    let repStr1 = 1, repStr2 = 1;

    for (let i = 0; i < Math.max(str1.length, str2.length); i++)
    {
        repStr1 *= (str1[i] && letters[str1[i]]) ? letters[str1[i]] : 1;
        repStr2 *= (str2[i] && letters[str2[i]]) ? letters[str2[i]] : 1;
    }

    return (repStr1 === repStr2);
};

console.log("[dog, goD] Anagrams?", isAnagram('dog', 'goD'));
console.log("[dogo, goD] Anagrams?", isAnagram('dogo', 'goD')); 
console.log("[Roast Beef, Eat for BSE] Anagrams?", isAnagram('Roast Beef', 'Eat for BSE'));
.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Advantages

  • Accepts anagrams of different lengths (check third example).
  • Is O(n) (only one loop is required).

Disadvantages

  • Won't work for large expressions, there will be an overflow on the generated number.
  • Needs a predefined dictionary between letters and primer numbers.
  • Won't work for expression that contains rare characters, unless you extend the dictionary, but the overflow will become more frequently.

Upvotes: 1

apple apple
apple apple

Reputation: 10591

You can try counting based algorithm.

const isAnagram = (str1, str2) => {

  str1 = str1.toLowerCase();
  str2 = str2.toLowerCase();
  //and remove any char you think not important (like space) here
  
  if (str1.length !== str2.length) return false
  
  let counting = {}
  for(let c of str1) 
     if(counting[c]) ++counting[c]
     else counting[c] = 1
  
  for(let c of str2)
     if(counting[c]) --counting[c]
     else return false
  
  return true
};

console.log(isAnagram('dog', 'goD')); //true
console.log(isAnagram('eleven plus two', 'twelve plus one')); //true
console.log(isAnagram('dog', 'hot')); //false
console.log(isAnagram('banana', 'nana')); //false

Upvotes: 5

Related Questions