3 ways to solve the Anagram Algorithm Problem

While studying up on algorithms, I found a particularly interesting and deceiving algorithm. It seemed easy yet I stumbled many times while trying to traverse towards a solution. Let me try to explain the problem and hopefully provide solutions that will help you think about algorithms differently.

What is an anagram?

a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

The anagram algorithm is a simple algorithm. Create a function where you compare two strings and check if they are anagrams of each other. The strings can contain any type of characters like “Hi, there!” and “There…hI!1!!!1”. The function should be able to sift through all the characters and confirm if both given strings are anagrams of each other.

Below, I wanted to give 3 solutions. The first solution being the solution I was able to come up with and the next two are others that I found that provided a much better and succinct way of solving it. I came upon the other two through this engineer, Stephen Grider, and his solutions helped me see how to get better at writing readable, efficient code.

First solution:

const anagrams = (stringA, stringB) => {
  const newStringA = stringA.replace(/[^\w]/g, '').toLowerCase()
  const newStringB = stringB.replace(/[^\w]/g, '').toLowerCase()
if (newStringA.length !== newStringB.length) { return false }
//create a hash map for both new words
  const objA = {},
        objB = {}
newStringA.split('')
  .forEach( char => {
    if(!objA[char]){
      objA[char] = 1
    } else {
      objA[char] += 1
    }
  })
newStringB.split('')
  .forEach( char => {
    if(!objB[char]){
      objB[char] = 1
    } else {
      objB[char] += 1
    }
  })
let result;
//compare both maps and see if keys values are equal
  for (let charA in objA){
    if(Object.keys(objB).includes(charA)){
      objA[charA] === objB[charA] ? result = true : result = false
    } else {
      result = false
    }
  }
return result
}

I first knew I had to remove all the characters that weren’t letters and then also convert them to the same letter case so that I could properly compare the two strings. I used some regex magic to get only the characters I need.

Then, I thought of automatically returning the function and not executing the rest if the string length themselves aren’t equal. If they aren’t equal, then I know for sure that anagrams of each other.

Best Coding Languages to Learn in 2019 | Data Driven Investor

The slightly complicated part was to create a hash map of the two strings and make key value pairs of each letter with their corresponding count. The goal here is to compare the count of the two objects and if they do, then return true, else return false.

What’s the problem with this solution?

The problem with this solution is that it is very verbose and there are things here that are repeated. The creation of the string and the hash maps are both repeated. I also was TOO explicit in creating a results variable. Also, checking if both hash maps had the same letters for keys could’ve been combined when checking for the number of values.

Second Solution:

const anagrams = (stringA, stringB) => {
  //build helper function to create specific maps
  //build a map per string
  //return false automatically if string lengths don't match
  //iterate through one map and check if the key value pairs match
  //if every test passes, return true at the end
  const aCharMap = buildCharMap(stringA);
  const bCharMap = buildCharMap(stringB);
  if (Object.keys(aCharMap).length !== Object.keys(bCharMap).length)     {return false}
  for (const char in aCharMap){
    if (aCharMap[char] !== bCharMap[char]){
      return false;
    }
   } 
  return true;
}
function buildCharMap(str){
  //create empty char map
  //iterate through each regex'd string. 
  //increment each key by one
  const charMap = {}
  for (let char of str.replace(/[^\w]/g, '').toLowerCase()){
    charMap[char] = charMap[char] + 1 || 1
  }
  return charMap
}

In this solution, the author created a helper function to create the character maps AND replace each string with just alphabets AND convert each to lower case. Helper functions are awesome because they reduce complexity from your main algorithms and helps make things more reusable and readable!

After creating the helper function he called it inside the main function to create a hash map for each.

Finally he created a for in loop and compared each object. If they were not equal, the function would return false. If it failed the conditional, the function would continue on and return true.

Third Solution:

function anagrams(stringA, stringB)
  // create helper function to clean up string
  // use function per string and compare them
  return cleanString(stringA) === cleanString(stringB)
}
function cleanString(str){
  return str.replace(/[^\w]/g, '').toLowerCase().split('').sort().join('');
}

This is the shortest of all the solutions. It creates a helper function that does the same replacement and changes the letter case. THE DIFFERENCE is that it creates an array with the letters AND sorts the array then converts it back to a string so that it makes it possible to check for strict equality between both strings.

This is short. This is clean. This is understandable.

It’s an awesome solution, but the problem is that it uses the sort method which increases the time complexity of the algorithm. Short, clean and understandable has it’s place in algorithms, but it’s not always the best solution.

Conclusion

To me, the second solution is my choice because of its efficiency and also still being readable. The anagram algorithm is a fun one and I hope I was able to introduce some topics that could help you be better at writing readable, efficient code!