A common algorithm question is:
Given two strings, check if they are anagrams of one another. If they are, return true; otherwise, return false.
An anagram is a word that is made up of the rearranged letters of another word. There are a few ways to approach this problem, and in this post I will walk through two of them: a short way, that involves using the 'sort' method, and a long way, that involves using hashes (I will be using JavaScript for both solutions).
The Short Way: Using Sort
This method involves cleaning up the string, splitting it into an array, sorting the array alphabetically, joining the array back into a string, and then checking if the two new strings are equal to one another.
To start out, initialize the variables and what will be returned at the end. Because we're checking if they are equal, and returning a boolean value, the return statement can simply check if the new variables are deeply equal.
function checkAnagramWithSort(str1, str2) {
let newStr1 = //...
let newStr2 = //...
return (newStr1 === newStr2)
}
This method requires cleaning up the string: what if there are capitalized letters? What if there are numbers or symbols? To remove those possibilities, first we will turn the string into lower case using the .toLowerCase() method, and then we will replace non-alphabetical characters using Regular Expressions. Anything that is not between 'a' and 'z' will be replaced by an empty string, effectively deleting its occurrence. We will do this for both of the parameters:
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '')//...
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '')//...
return (newStr1 === newStr2)
}
At this point, we have two new strings that are all lower case and have no instances of non-alphabetic characters in them. In order to use the .sort() method, we will have to turn the strings into arrays using .split(''). Unless specified otherwise, when used with alphabetical characters, arrays are sorted alphabetically from A-Z. If the two words are anagrams, then the letters will end up in the same order using this method.
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '').split('').sort()//...
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '').split('').sort()//...
return (newStr1 === newStr2)
}
The last thing we have to do is turn them back into strings. In JavaScript, Objects (including arrays) cannot be evaluated as equal to one another, even if they contain the exact same values. Two strings, on the other hand, can be evaluated in this way. Therefore, calling the .join() method at the end will enable the return function to work.
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '').split('').sort().join('')
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '').split('').sort().join('')
return (newStr1 === newStr2)
}
The Long Way: Using Hashes
This approach uses some of the similar methods to the approach above, particularly in terms of cleaning up the string, but then creates two hashes that has keys that are the letters of each string, and values that represent how many times they appear in the string.
To start, initialize the function, and then use the same string cleaning up methods used above:
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '')
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '')
//...
}
The first thing to test for is to see if the lengths of these new variables are equal to one another. If they're not equal, then they cannot be anagrams, and therefore you can return false right away.
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '')
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '')
if (newStr1.length !== newStr2.length) {
return false
}
//...
}
Then, initialize two new hashes that will contain the characters of both strings.
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '')
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '')
if (newStr1.length !== newStr2.length) {
return false
}
let hash1 = {}
let hash2 = {}
//...
}
Now, we'll go through each of the strings and check if each letter in the string is already in the hash. If it is, add 1 to the value. If not, initialize the key-value pair with a value of 1.
In order to go through the strings, we have to split them using .split() and map over them.
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '')
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '')
if (newStr1.length !== newStr2.length) {
return false
}
let hash1 = {}
let hash2 = {}
newStr1.split('').map(letter => {
//Here I use a ternary because I think it looks neater, but this could just as easily be written as a typical if-else statement:
//if (hash1[letter]) { hash1[letter] = hash1[letter]+1 } else { hash1[letter] = 1}
hash1[letter] ? hash1[letter]++ : hash1[letter] = 1
})
newStr2.split('').map(letter => {
hash2[letter] ? hash2[letter]++ : hash2[letter] = 1
})
//...
}
Next, we'll initialize two new variables using the Object.keys() method. This method takes in one argument, which is an object, and returns an array of the keys of that Object. In this function, it will return an array of the letters of the string without any duplicates. Therefore, if newStr1 was 'racecar', this array would be ['r', 'a', 'c', 'e'].
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '')
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '')
if (newStr1.length !== newStr2.length) {
return false
}
let hash1 = {}
let hash2 = {}
newStr1.split('').map(letter => {
hash1[letter] ? hash1[letter]++ : hash1[letter] = 1
})
newStr2.split('').map(letter => {
hash2[letter] ? hash2[letter]++ : hash2[letter] = 1
})
let hash1keys = Object.keys(hash1)
let hash2keys = Object.keys(hash2)
//...
}
Now we finally can do the actual checking. Using a for loop, we'll go through the hash1keys array. For each element of the array (a letter), we will check to see if that same letter can be found in hash2keys array using .includes(). If not, we can immediately return false. Otherwise, we will proceed, and will check to see if that element's value in hash1 is the same as that element's value in hash2. If it is not, then return false.
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '')
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '')
if (newStr1.length !== newStr2.length) {
return false
}
let hash1 = {}
let hash2 = {}
newStr1.split('').map(letter => {
hash1[letter] ? hash1[letter]++ : hash1[letter] = 1
})
newStr2.split('').map(letter => {
hash2[letter] ? hash2[letter]++ : hash2[letter] = 1
})
let hash1keys = Object.keys(hash1)
let hash2keys = Object.keys(hash2)
for (let i = 0; i<hash1keys.length; i++) {
if (!hash2keys.includes(hash1keys[i])) {
return false
}
if (hash1[hash1keys[i]] !== hash2[hash1keys[i]]) {
return false
}
}
//...
}
Finally, if after all of these tests, false was never returned, then return true.
function checkAnagramWithSort(str1, str2) {
let newStr1 = str1.toLowerCase().replace(/[^a-z]/g, '')
let newStr2 = str2.toLowerCase().replace(/[^a-z]/g, '')
if (newStr1.length !== newStr2.length) {
return false
}
let hash1 = {}
let hash2 = {}
newStr1.split('').map(letter => {
hash1[letter] ? hash1[letter]++ : hash1[letter] = 1
})
newStr2.split('').map(letter => {
hash2[letter] ? hash2[letter]++ : hash2[letter] = 1
})
let hash1keys = Object.keys(hash1)
let hash2keys = Object.keys(hash2)
for (let i = 0; i<hash1keys.length; i++) {
if (!hash2keys.includes(hash1keys[i])) {
return false
}
if (hash1[hash1keys[i]] !== hash2[hash1keys[i]]) {
return false
}
}
return true
}
There are certainly more approaches out there! Feel free to post your solution in the comments.
Top comments (0)