One Simple Way To Solve the Anagram Problem
If you, like me, are a recent college grad with a liberal arts degree in English who has basically spent her entire life avoiding math you might also find the idea of solving “algorithms”(I mean, what does that word even mean???) incredibly daunting.
However, after joining leet code and getting a few practice problems under my belt, I can assure you that learning to solve algorithms is absolutely not as hard as you think it will be. In fact, I’ve even started to find it… fun?!
So, to get you started, I am going to walk you through my simple solution to the valid anagram problem . (Anagram = a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.)
The problem:
Given two strings s and t , write a function to determine if t is an anagram of s.
Examples:
Input: s = "anagram", t = "nagaram"
Output: trueInput: s = "rat", t = "car"
Output: false
Getting started:
Through the help of my friend Stephen Keating, I know that a good way to solve this is problem is through creating a character map for each of our given strings.
You might already be a little lost (don’t worry, I was too!), but basically, a character map allows us to keep track of how many times a given character in each string has been repeated throughout the string. Since anagrams will have the same exact characters occurring at the same exact frequency, keeping track of each character and the frequency at which it occurs in a string will be essential for solving this problem.
For example, if we were given the word “hello”, our character map would look something like this:
{ h: 1, e: 1, l: 2, o: 1 } Now that we understand why creating a character map will be helpful, let’s go through how to create said map using our helpful for/of loop.
Creating a character map with a for/of loop:
A for/of loop is really useful tool in Javascript that allows us to iterate over an array or a string (It’s similar to the for/in loop, which we will use later in our final solution to this problem!).
To create a character map using a for/of loop, we will start out by creating an empty hash/object to store our mapped characters. In the example below, I called this “strHash”.
Then, using our for/of loop, we will iterate over each character in the string and if that character already exists in strHash we will increment the number of instances of that character, otherwise we will create a key in strHash at that character with a value of one:
let strHash = {}for (let char of str) {
if (strHash[char]) {
strHash[char] += 1
} else {
strHash[char] = 1
}
}
Awesome! Now that we know how to write a character map, we can continue solving this problem.
For/in loop:
Remember above when I said that we were also going to use a for/in loop to solve this problem? Well, now is that time for that.
Javascript’s for/in loop works very similarly to the for/of loop, however it is primarily used for iterating over objects (such as our character maps).
We will use the for/in loop to compare the values of keys for the character maps for each of our given strings. As you might be able to guess, if the strOneHash at a given character (key aka “k” in my example below) has the same value as strTwoHash at the same character, then the two strings will have same number of frequency of characters and will thus, be considered valid anagrams.
for (let k in strOneHash) {
if (strOneHash[k] !== strTwoHash[k] {
return false
}
}The solution:
Now that we have gone over two super important steps for solving this problem, let me walk you through my final solution:
createCharMap = (str) => {
let strHash = {}
for (let char of str) {
if (strHash[char]) {
strHash[char] += 1
} else {
strHash[char] = 1
}
}
return strHash
}isAnagram = (s, t) => { let charMapS = createCharMap(s)
let charMapT = createCharMap(t) if (s.length !== t.length){
return false
}
for (let k in charMapS) {
if (charMapS[k] !== charMapT[k]) {
return false
}
}
return true
};
The first thing I did was create a function to create character maps for each given string. While you could create two for/of loops in your isAnagram function to create character maps for each given string, I find making a separate function allows me to have slightly cleaner and DRYer code (however, either solution is valid!).
Next, I wrote my isAnagram function. You will see that the first part of that function just calls on my createCharMap function for each of our two given strings, s and t and assigns the return value (NEVER FORGET TO RETURN!!!) of that function to a variable.
Next, my isAnagram function checks the lengths of each string and returns false if the strings are not the same length. This part of the code is necessary for edge cases such as s = “hello” and t = “hellos”. Without this if statement, my following for/in loop will not take into account the extra character in charMapT and won’t return false as charMapS at each k (h, e, l, and o) will have the same value as charMapT at the same keys.
Finally, if s and t have the same number of characters, my for/in loop will run and compare the values of each key as we discussed above. If the value at the same key in each character map is different, my function will return false and if not, the function will return true and we will know that our strings are valid anagrams of each other.
Conclusion:
I hope you found this walk through helpful. Algorithms (and coding, for that matter) can seem really intimidating before you get started, however I hope you don’t let that stop you. Take it from me, the best way to feel more comfortable (and get better at) solving algorithm problems is to just get started!
