• 0

Determine if given strings are anagram.

Input : Two strings // 'dog', 'god' ; 'foo','bar'
Output : Boolean // True ; False

Clarifications :
  • Is the comparison of our string permutation case sensitive? Yes
  • Is whitespace significant? Yes

Approach 1 :

Logic :

  • If both the strings are of different lengths then they can not be permutations of each other. Hence, return false.
  • Sort both the strings.
  • Compare both the sorted strings.

Time Complexity :

  • O(N log N); where N is the length of the string

Solution :


function isAnagram (str1, str2) {
if (str1.length !== str2.length) {
return false;
}
var sortStr1 = str1.split('').sort().join('');
var sortStr2 = str2.split('').sort().join('');
return (sortStr1 === sortStr2);
}
console.log(isAnagram('dog','god')); // true
console.log(isAnagram('foo','bar')); // false
console.log(isAnagram('foo','fooo')); // false

Approach 2 :

If you have to provide solution in linear time O(N); where N is the length of the string or
If you are not allowed to use inbuilt methods of JavaScript then you can use this approach.

Logic :

  • If both the strings are of different lengths then they can not be permutations of each other. Hence, return false.
  • Create character count for string 1.
  • Compare the character count for string 1 with string 2.

Time Complexity :

  • O(N); where N is the length of the string

Solution :


function isAnagram (str1, str2) {
if (str1.length !== str2.length) {
return false;
}
// create a character count for the string
var str1Count = {};
Array.prototype.forEach.call(str1, function(ch) {
str1Count[ch] = str1Count[ch] ? 1 + str1Count[ch] : 1;
});
// compare the character count with the second string
var str2len = str2.length;
for (var i = 0; i < str2len; i++) {
if(!str1Count[str2[i]]) {
return false;
} else {
str1Count[str2[i]] -= 1;
}
}
return true;
}
console.log(isAnagram('dog','god')); // true
console.log(isAnagram('foo','bar')); // false
console.log(isAnagram('foo','fooo')); // false
view raw is-permute.js hosted with ❤ by GitHub