patternjavascriptMajor
Determining if two words are anagrams
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:
EDIT: A speed comparison between using a hash and using a 26-value array:
http://jsperf.com/anagram-algorithms
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.