Javascript Algorithms #2: Palindromes

Palindromes! Palindromes!! Palindromes!!! Ooooh boy. I'm pretty sure that by now you are wondering what these are. You know personally as a software developer when someone utters 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 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 seems 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 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 unique ways to implement this below:

The Intuitive Approach

Okay, i must confess the title sounds a bit misguiding. 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 palindrome(text) {
// Split, reverse and join string to get reversed text
var reversedText  = text.toLowerCase()
                    .split('').reverse().join('');


return text === reversedText;


}

I'm sure there's someone 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. Weird punctuation, I know! smiles

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 palindrome(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
}

 Dramatic sound effect here…lol… I'm really just too playful.

Well, i'm sure 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. I'd really like you to try your hands on optimizing this. I'll be posting the solution in the comment section and on twitter after seeing what you could come up with.
Have fun while at it!

Evaluation & Summary

We've now examined two ways to implement a palindrome checker in Javascript. Both implementations are okay and could help you pass that coding interview.

However as is our concern in this case, we need to determine which has higher performance characteristics as we take a look at their pros and cons.

In my next article i will explore more ways to implement this algorithm as we consider other stricter variations of palindromes, then we'd run a performance test to determine the most highly performant.

---

Feel free to implement this in other ways and explore the pros and cons of using each method. Also share them with everyone 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.

Please share this article with other's too if you found it helpful. You received freely, give freely. I also won't mind a round of applause you know (winks).
Clap so others get to enjoy this too!

Connect with me on twitter will you? @worldclassdev

SUBSCRIBE HERE FOR UPDATES & STAY TUNED FOR THE NEXT ARTICLE ON THE SERIES.

Comments

[Kushan Joshi]

Great explanation Justine, especially using the .each API. Since javascript is so versatile, I am adding one more solution which uses iterator from my previous article dev.to/kepta/how-i-learned-to-stop...

function isPalindrome(str) {
   const iter = [...str.toLowerCase()];
   for (let char of iter) {
      if (char !== iter.pop()) { return false}
   }
   return true
}

The good thing about this is that it iterates only over half of the string to check if it is palindrome.

[jean luc tuyishime]

Do you have an idea on how you can do permutation of palindrome??

[Saurabh Sharma]

those memories of solving algorithms at freecodecamp.org

const isPalindrome = str => str.toLowerCase() === str.toLowerCase().split().reverse().join() 

[Mahmoud Aslan]

nice, somehow didn't work until i added the splitters for split() and join()

const isPalindrome = str => str.toLowerCase() === str.split('').reverse().join('')

[Saurabh Sharma]

thats why we needs unit tests 😅

[Philip Obosi]

Thanks for the save. I didn't even look at the syntax closely. It's still a pretty concise solution though

[Philip Obosi]

Clean and concise

[Steveen Echeverri]

Palindrome example for a word, phrase, number or sequence of characters:

const isPalindrome = str => [...`${str}`].reverse().join('') == str;

[Kenthmordecai]

Great!