Algorithm Problem Review #3: Anagram
This week I was working on another algorithm problem from my Colt Steele Udemy course. This is another frequency counter type problem but this time I’m working to see if two strings are anagrams of each other.
Frequency Counter — validAnagram
Given two strings, write a function to determine if the second string is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, such as “cinema”, formed from “iceman.”
Example
Inputs: string1=“ ” , string2=“ ”
Output: true
Inputs: string1=“aaz” , string2=“zza”
Output: false
Inputs: string1=“anagram” , string2=“nagaram”
Output: true
Inputs: string1=“awesome” , string2=“awesom”
Output: false
Constraints
- All inputs are single words
- All inputs are lowercase
- None of the inputs have spaces, punctuations, or numbers
function validAnagram(string1, string2){}
My Process
Understanding the Problem
Before starting to code, lets restate the problem. I need to create a function that will tell me if my two string inputs string1 and string2 are anagrams of each other. If they are anagrams my function must return true if they are not anagrams, my function must return false. My strings will be single words that don’t have spaces, numbers, punctuations and all lowercased.
Breaking it Down
Time to comment the things I need to do for this problem.
function validAnagram(string1, string2){
// Do something... /* return true if string1 and string2 are anagrams, return false otherwise */}
My first plan of action in my “Do something…” section, is to check if the two strings were the same length, if they weren’t then I would automatically return false. Then next is to create an object that has the keys of the letters of string1 with the values of the amount of times they appear in that word. And then making another object doing the same thing but with string2.
function validAnagram(string1, string2){
if (string1.length !== string2.length){
return false
} // 1. Create empty objects
let stringFreq1 = {}
let stringFreq2 = {} // 2. Loop through string1 and then string2 to add to the objects /* return true if string1 and string2 are anagrams, return false otherwise */}
I want my objects to look like this.
EXAMPLE
inputs: validAnagram('anagram', 'nagaram')stringFreq1 = {'a':3, 'n':1, 'g':1, 'r':1, 'm': 1}
stringFreq2 = {'n':1, 'a':3, 'g':1, 'r':1, 'm': 1}
So I’ll be using a for…of loop this time to loop through my two strings. If the letter in the string is already a key in the object, I will add 1 to the value. If not then I will set it to 0 and add 1. Then I am going to compare the keys and values of both objects to each other.
function validAnagram(string1, string2){
if (string1.length !== string2.length){
return false
} // 1. Create empty objects
let stringFreq1 = {}
let stringFreq2 = {} // 2. Loop through string1 and then string2 to add to the objects
for (let letter of string1){
stringFreq1[letter] = (stringFreq1[letter] || 0) + 1
} for (let letter of string2){
stringFreq2[letter] = (stringFreq2[letter] || 0) + 1
} // 3. Compare the keys and values in both objects /* return true if string1 and string2 are anagrams, return false otherwise */}
Now that my objects are created, I will compare the key values in both objects to see if they don’t have the exact same keys, if so it will return false immediately. Then if they don’t have the same values for those keys, if so it will return false immediately. If it doesn’t return false for either of those tests then it will return true and both strings are true anagrams of each other.
I will be using the for…in to loop over my objects
function validAnagram(string1, string2){
if (string1.length !== string2.length){
return false
} // 1. Create empty objects
let stringFreq1 = {}
let stringFreq2 = {} // 2. Loop through string1 and then string2 to add to the objects
for (let letter of string1){
stringFreq1[letter] = (stringFreq1[letter] || 0) + 1
} for (let letter of string2){
stringFreq2[letter] = (stringFreq2[letter] || 0) + 1
} // 3. Compare the keys and values in both objects
for (let key in stringFreq1){ // 3a. checking if the keys of stringFreq1 are missing from stringFreq2
if(!(key in stringFreq2)){
return false
} // 3b. checking if the key's value of stringFreq1 is different from the key's value in stringFreq2
if (stringFreq2[key] !== stringFreq1[key]){
return false
}
} /* return true if string1 and string2 are anagrams, return false otherwise */
return true}
SOLVED
function validAnagram(string1, string2){
if (string1.length !== string2.length){
return false
} let stringFreq1 = {}
let stringFreq2 = {} for (let letter of string1){
stringFreq1[letter] = (stringFreq1[letter] || 0) + 1
} for (let letter of string2){
stringFreq2[letter] = (stringFreq2[letter] || 0) + 1
} for (let key in stringFreq1){ if(!(key in stringFreq2)){
return false
} if (stringFreq2[key] !== stringFreq1[key]){
return false
} } return true}
My Thoughts
This was a fairly simple problem which helped me reinforce working with objects to avoid nested looping with problems concerning the frequency of something. This function has an O notation of O(n) which is pretty decent.
