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 :
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 :
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |