HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavascriptMajor

Determining if two words are anagrams

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
determininganagramsarewordstwo

Problem

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

Solution

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

Code Snippets

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

Context

StackExchange Code Review Q#99247, answer score: 28

Revisions (0)

No revisions yet.