Determining if two words are anagrams

Question

I was given a this problem at a technical interview and failed miserably in the time given. Afterwards, I sat down and worked out what I think is a good solution. The task was actually to build an AngularJS app to do this, which I did, but the guts of my solution is in JavaScript. I wanted to ask if there is a better way to do this:

// convert strings to LC for case insensitivity
// split strings into arrays
// sort the arrays (spaces will sort first and be trimmed later)
// join the arrays back into strings
// we're only concerned about the printable characters in the anagram so,
// trim() to remove any spaces and then compare the resulting strings
var str1 = this.word1.toLowerCase().split('').sort().join('').trim();
var str2 = this.word2.toLowerCase().split('').sort().join('').trim();

if (str1 === str2) {
    this.isAnagram = true;
} else {
    this.isAnagram = false;
}

Answer 1

My original assertion (Outdated):

Sorting a string (Or any array) is inefficient because even the fastest algorithm will sort no faster than O(n log n) in an average case. The most efficient way would use a hash map to count letters in each word. Something like:

Although reading from a hash map can be as quick as O(1), writing to a hash map is significantly slower. By using a 26-value array (0-25) to represent lowercase letters, the speed of operations can be sped up significantly:

function isAnagram(word1, word2) {
  if (typeof word1 !== 'string' || typeof word2 !== 'string') {
    throw new Error('isAnagram requires two strings to be passed.')
  }

  var normalizedWord1 = word1.replace(/[^A-Za-z]+/g, '').toLowerCase();
  var normalizedWord2 = word2.replace(/[^A-Za-z]+/g, '').toLowerCase();

  var counts = [];
  var word1Length = normalizedWord1.length;
  var word2Length = normalizedWord2.length

  if (word1Length !== word2Length) { return false; }

  for (var i = 0; i < word1Length; i++) {
    var index = normalizedWord1.charCodeAt(i)-97;
    counts[index] = (counts[index] || 0) + 1;
  }

  for (var i = 0; i < word2Length; i++) {
    var index = normalizedWord2.charCodeAt(i)-97;
    if (!counts[index]) { return false; }
    else { counts[index]--; }
  }

  return true;
}

EDIT: A speed comparison between using a hash and using a 26-value array: http://jsperf.com/anagram-algorithms

Answer 2

Everybody is talking about your algorithm, but everybody does the same mistake.

Repeated code! Yeah, you have repeated code.

Look at the following lines:

var str1 = this.word1.toLowerCase().split('').sort().join('').trim();
var str2 = this.word2.toLowerCase().split('').sort().join('').trim();

Just look how long that is! And repeated! Move that to a new function:

var regularize = function(str) {
    return str.toLowerCase().split('').sort().join('').trim();
}

And now you can do like this:

var str1 = regularize(this.word1);
var str2 = regularize(this.word2);

But you have this a few lines below:

if (str1 === str2) {
    this.isAnagram = true;
} else {
    this.isAnagram = false;
}

So, you don't need those variables or anything... Cleaning up, you can just do:

this.isAnagram = regularize(this.word1) == regularize(this.word2);

---

As suggested many times before, you can do some cleanup to the string. Regular expressions come to my mind. Based on @Tushar's answer, I came up with this:

var regularize = function(str) {
    return str.toLowerCase().replace(/[^a-z\d]/g,'').split('').sort().join('');
}

---

All assembled together:

var regularize = function(str) {
    return str.toLowerCase().replace(/[^a-z\d]/g,'').split('').sort().join('');
}
this.isAnagram = regularize(this.word1) == regularize(this.word2);

Pretty short, isn't it?

Answer 3

Your solution is not removing punctuations and spaces before checking if two strings are Anagrams.

Also, the code can be optimized.

1. First, remove all the spaces and punctuation marks from both the strings using Regular Expression
2. Check if the length of strings are equal, if not return false immedietly
3. Check for Anagrams only when both strings are of equal length.

Code:

var regex = /[^a-z0-9]/gi;

var str1 = this.word1.replace(regex, ''),
    str2 = this.word2.replace(regex, '');

this.isAnagram = str1.length > 0 && str1.length === str2.length && (str1.toLowerCase().split('').sort().join('') === str2.toLowerCase().split('').sort().join(''));

This will first check for the length of strings are equal, if equal then only (str1.toLowerCase().split('').sort().join('') === str2.toLowerCase().split('').sort().join('')) is evaluated.

Regex Explanation

1. /: Delimiter of regex
2. []: Character class
3. [^..]: Not containing any of the following characters
4. a-z0-9: All alphanumeric characters
5. g: Global flag. Matches all the characters from the class
6. i: Case insensitive match

Demo

var regex = /[^a-z0-9]/gi;
document.getElementById('btn').addEventListener('click', function() {

  var str1 = (document.getElementById('str1').value).replace(regex, ''),
    str2 = (document.getElementById('str2').value).replace(regex, '');

  var isAnagram = str1.length > 0 && str1.length === str2.length && (str1.toLowerCase().split('').sort().join('') === str2.toLowerCase().split('').sort().join(''));

  alert('Is Anagram: ' + isAnagram);
}, false);

<input type="text" id="str1" />
<br />
<input type="text" id="str2" />
<br />
<input type="button" id="btn" value="check" />

Edit

Another approach:

var checkAnagram = (function () {
    var sanitizeRegex = /[^a-z0-9]/gi;

    var sanitizeString = function (str) {
        return str.replace(sanitizeRegex, '').toLowerCase().split('').sort().join('');
    };

    return function (str1, str2) {
        return sanitizeString(str1) === sanitizeString(str2);
    };
}());

var isAnagram = checkAnagram('Rust! Ha?', 'Tushar'); // Usage

Demo

Answer 4

I have some boilerplate code similar to rrowland's, but I feel like my algorithm could be a little bit faster. It operates in O(n) by using prime number multiplication to count letters, and is non-branching in the longest-time routine.

Instead of doing ind - 97 I keep 97 empty spots in the array that is accessed.

I think if you were more obsessive you could do the counting using bitwise operations, but this is good enough.

function isAnagram(word1, word2) {
  if (!word1 || !word2 || !word1.length || !word2.length) {
    throw new Error('isAnagram requires two strings to be passed.')
  }

  var nword1 = word1.replace(/\s+/g, '').toLowerCase();
  var nword2 = word2.replace(/\s+/g, '').toLowerCase();

  var length1 = nword1.length;
  var length2 = nword2.length;

  if (length1 !== length2) {
    return false;
  }

  var word1hash = 1;
  var word2hash = 1;

  var primes = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101];

  var ind;
  for (var i = 0; i < length1; i++) {
    ind = nword1.charCodeAt(i);
    word1hash *= primes[ind];
  }

  for (var i = 0; i < length2; i++) {
    ind = nword2.charCodeAt(i);
    word2hash *= primes[ind];
  }

  console.log(word1hash);
  console.log(word2hash);

  return word1hash == word2hash;
}

---

Edit 1

I guess we have a speed contest now, and this version is a great deal faster than all its precedents (benchmark).

function isAnagram(word1, word2) {
  if (!word1 || !word2 || !word1.length || !word2.length) {
    throw new Error('isAnagram requires two strings to be passed.')
  }

  var nword1 = word1;
  var nword2 = word2;

  var length1 = nword1.length;
  var length2 = nword2.length;

  if (length1 !== length2) {
    return false;
  }

  var word1hash = 1;
  var word2hash = 1;

  var tab = {'q': 2, 'w': 3, 'e': 5, 'r': 7, 't': 11, 'y': 13, 'u': 17, 'i': 19, 'o': 23, 'p': 29, 'a': 31, 's': 37, 'd': 41, 'f': 43, 'g': 47, 'h': 53, 'j': 59, 'k': 61, 'l': 67, 'z': 71, 'x': 73, 'c': 79, 'v': 83, 'b': 89, 'n': 97, 'm': 101, 'Q': 2, 'W': 3, 'E': 5, 'R': 7, 'T': 11, 'Y': 13, 'U': 17, 'I': 19, 'O': 23, 'P': 29, 'A': 31, 'S': 37, 'D': 41, 'F': 43, 'G': 47, 'H': 53, 'J': 59, 'K': 61, 'L': 67, 'Z': 71, 'X': 73, 'C': 79, 'V': 83, 'B': 89, 'N': 97, 'M': 101, ' ': 1}

  for (var i = 0; i < length1; i++) {
    word1hash *= tab[word1[i]]
  }

  for (var i = 0; i < length2; i++) {
    word2hash *= tab[word2[i]]
  }

  return word1hash == word2hash;
}

---

Edit 2

I know this is silly, but adding logarithms of prime numbers is actually a tiny bit faster. (benchmark)

function isAnagram(word1, word2) {
  if (!word1 || !word2 || !word1.length || !word2.length) {
    throw new Error('isAnagram requires two strings to be passed.')
  }

  var length1 = word1.length;
  var length2 = word2.length;

  var word1hash = 1;
  var word2hash = 1;

  var tab = {'q': 0.6931471805599453, 'w': 1.0986122886681098, 'e': 1.6094379124341003, 'r': 1.9459101490553132, 't': 2.3978952727983707, 'y': 2.5649493574615367, 'u': 2.833213344056216, 'i': 2.9444389791664403, 'o': 3.1354942159291497, 'p': 3.367295829986474, 'a': 3.4339872044851463, 's': 3.6109179126442243, 'd': 3.713572066704308, 'f': 3.7612001156935624, 'g': 3.8501476017100584, 'h': 3.970291913552122, 'j': 4.07753744390572, 'k': 4.110873864173311, 'l': 4.204692619390966, 'z': 4.2626798770413155, 'x': 4.290459441148391, 'c': 4.3694478524670215, 'v': 4.418840607796598, 'b': 4.48863636973214, 'n': 4.574710978503383, 'm': 4.61512051684126, 'Q': 0.6931471805599453, 'W': 1.0986122886681098, 'E': 1.6094379124341003, 'R': 1.9459101490553132, 'T': 2.3978952727983707, 'Y': 2.5649493574615367, 'U': 2.833213344056216, 'I': 2.9444389791664403, 'O': 3.1354942159291497, 'P': 3.367295829986474, 'A': 3.4339872044851463, 'S': 3.6109179126442243, 'D': 3.713572066704308, 'F': 3.7612001156935624, 'G': 3.8501476017100584, 'H': 3.970291913552122, 'J': 4.07753744390572, 'K': 4.110873864173311, 'L': 4.204692619390966, 'Z': 4.2626798770413155, 'X': 4.290459441148391, 'C': 4.3694478524670215, 'V': 4.418840607796598, 'B': 4.48863636973214, 'N': 4.574710978503383, 'M': 4.61512051684126, ' ': 0.0
}

  for (var i = 0; i < length1; i++) {
    word1hash += tab[word1[i]]
  }

  for (var i = 0; i < length2; i++) {
    word2hash += tab[word2[i]]
  }

  return word1hash == word2hash;
}

Edit 3: removed equal length check.

Answer 5

I have an easy example

function isAnagram(strFirst, strSecond) {

 if(strFirst.length != strSecond.length)
       return false;

 var tempString1 = strFirst.toLowerCase();
 var tempString2 = strSecond.toLowerCase();

 var matched = true ;
 var cnt = 0;
 while(tempString1.length){
    if(tempString2.length < 1)
        break;
    if(tempString2.indexOf(tempString1[cnt]) > -1 )
        tempString2 = tempString2.replace(tempString1[cnt],'');
    else
        return false;

    cnt++;
 }

 return matched ;

 }

Calling function will be isAnagram("Army",Mary); Function will return true or false