Javascript Algorithms #2: Palindromes

Palindromes!!! As a software developer when someone utters seemingly complex words like this while communicating with me, i gesture awkwardly and give a pretty obnoxious smirk to indicate some level of disinterest. I’m really not a fan of confusing people.

Seat belts on? Let’s do justice to the big word. Shall we?

A palindrome is a word, number, or other sequence of characters which reads the same backward as forward, such as “madam” or “racecar”. Using a bit of programmer’s speak we could say it’s a string of text that doesn’t change when re-arranged in reverse(the opposite direction).
So much for the big word huh?

The Challenge

Given a string of text, return true or false indicating whether or not the text is a palindrome.

PS: I remember taking this challenge once during Andela’s assessment test.

Algorithmic Logic

The challenge says “given a string of text” which implies that our function would have a string-typed parameter which we may call “text”. Next, we are to evaluate if the string is a palindrome. To do this, we’ll have to reverse the string first and then compare it with the string that was passed in as an argument.
To avoid issues with letter casing, it’d be reasonable to convert text to a single case type, be it upper or lower. Finally, we are to “return true or false” depending on the result of our evaluation. True for when it is a palindrome and false for otherwise.

All said! You shall now proceed to the Code Dojo.

Code Implementation

There’s quite a handful of approaches to implementing a palindrome checker and this is mostly due to the fact that there are several ways to reverse a string and several ways to loop through a string. Hence, there’s a couple of stunts and combos one could pull off. However we’d consider two, yet three unique ways to implement this below:

The Intuitive Approach

Okay, i must confess the title sounds a bit misleading. This isn’t exactly the first thing everyone would do if they are presented with this challenge. It’s really just a direct approach to solving the problem. How direct? You’d see.

/*
The Intuitive Approach: This is mostly a direct
approach that most would follow. We split the
string into characters, reverse the array of characters,
join the characters back to form a string, and then
test the created string against what was originally received.
*/
function palindromeIntuitive(text) {
// Split, reverse and join string to get reversed text
var reversedText  = text.toLowerCase()
                    .split('').reverse().join('');


return text === reversedText;


}

I’m sure you might be thinking “this really isn’t direct at all”. Oh well! Let’s unveil the “mysteries”, shall we?

  • First our function accepts a parameter which is the string of text which is to be tested.
  • Next, we convert all letters of the string to lowercase, then call the .split() method on the string that is received and pass it an empty string in order to spread the characters into and array.
  • Next, we call .reverse() on the array to re-order its elements in reverse.
  • After that we call .join() on the reversed array to form a string once again.

Voila! we have a reversed string. Notice how we chained all these methods in succession making our code concise yet functional. This is one of the reasons i love Javascript. Elegant syntax!

At the end we return the result of our comparison which is a boolean indicating if the string that was passed in equals the reversed string we created. This tells us if the text that was passed in is a palindrome.
Capiche!!! That was easy wasn’t it?
Let’s try something slightly more complex.

Looping through and Comparing Characters

Hmmmmmm! I did call this a slightly complex implementation.

Disclaimer: This could be a bit more confusing than you expected. But i’ll break it down to the best of my ability. So, fear not!

Following this approach we try to loop through the string as it was passed in and compare each character with the character currently in the position it’d have taken if the string was reversed.

For example if we were testing the string “developer”, we would compare “d” with “r” because if the string was reversed d would take r’s position.

Correspondingly we’d compare “e” in position 2 with “e” in position 2 from the end as well. If the string were a palindrome, all of these would test true.
Alright now! Let the code speak for itself.

/*
Looping and Comparing using .every(): This approach allows us to
split the sting into an array of characters and then loop through
the characters comparing them with the characters in their
corresponding positions from the right.
*/
function palindromeLoop(text) {
// Split text into array of characters
let charArray = text.toLowerCase().split('');


// Loop through every character and compare with the
// character in its corresponding position if the string
// was reversed. Then store the result
let result = charArray.every((letter, index) => {
return letter === charArray[charArray.length - index - 1];
});


// Return the result of the evaluation
return result
}

By now you must’ve noticed that learning to do amazing things with core Javascript is a fun and adventurous process. Alright, let’s do the review thing.

  • We converted all letters of the string to lowercase, then used .split() once again to spread the characters of the string into an array.
  • Next we use a special array method .every() to loop through the array an perform our check. Basically, the .every() method tests whether all elements in the array pass the test implemented by the provided function. The provided function in our case accepts the current letter and its index in the array as parameters. Then we return the result of the comparison between the letter and the letter currently occupying the position this letter would assume if the string was reversed. Learn more about .every() here.
  • Cumulatively, the .every() method would evaluate to true if the test passes in all cases and false if it didn’t. The result of that evaluation is what we store in the variable “result” and that’s what our function returns as an indication that the string failed or passed the palindrome check.

Perhaps you noticed too? There’s something intrinsically wrong with our second implementation performance-wise. Maybe try identifying it by yourself before you proceed with the rest of the article?Okay, here it is. We loop through the entire string and compare every letter with the corresponding letter in its position in reverse. Maybe take out a pen and paper and try to do this manually, then you’d notice that once you loop beyond the string holding the middle position, you are intrinsically repeating comparisons you’ve already gone through in the first half of the iteration. That’s redundant, don’t you think?

In order to fix this, we’d add a check to ensure that we stop looping once we get to the mid-point of the string. Perhaps take a break from reading and try this out,  I’d encourage you to try your hands on optimizing this.

The Fix

In this solution we use a for-loop to iterate through the string of text only up till the mid point while comparing characters from the left of the string with the character in its corresponding position from the right.


function palindromeLoopFix(text) {
 var textLen = text.length;
 for (var i = 0; i < textLen/2; i++) {
   if (text[i] !== text[textLen - 1 - i]) {
       return false;
   }
 }
 return true;
}

Evaluation & Summary

We’ve now examined two ways to implement a palindrome checker in Javascript. Both implementations get the job done and could help you pass that coding interview.

The intuitive approach is perhaps the way to go for most Javascript developers, however Javascript offers more than one way to achieve most things.

As performance is our concern in the case this test on jsperf.com  reveals that the optimized looping method out-performs the intuitive approach by 2.21%. Perhaps insignificant in most cases but in performance, every minor cut is a win.


Feel free to implement this in other ways and explore the pros and cons of using each method. Also share your solutions in the comment section (possibly a link to your pen). We look forward to seeing them. Ask questions as well. I’m sure we’d be able find the answers somehow.

Checkout the previous challenge: Counting The Vowels in a String of Text