Algorithms : Palindromes in 4 ways

Check if a string is a palindrome in four ways.

Photo by Evgeny Tchebotarev from Pexels

Today I woke up quite satisfied as I realized it’s a palindrome date: 02–02–2020. Palindrome is a word, number or a phrase that reads the same forwards as well as backwards, for instance “kayak”, “1001”, “Was it a car or a cat I saw?”, or “ABBA”. I love palindromes — read more on why they are fun on this Wikipedia page. Did you know that the longest palindrome was 58,795 letters long? Also, you can use this wonderful poem for tests: Dammit I’m Mad by Demetri Martin, where every line is a palindrome, as well as a whole poem itself!

Welcome to my algorithms series where I explain how to tackle common algorithmic issues. Today we will create an algorithm that will check if a given word is a palindrome. I present three solutions, sorted by the least to the most performant.

Setup: Regex

If you want to be extra fancy, you can begin with thinking about edge cases. What if your example includes spaces, letters of different capitalization, or interpunction marks? This is not required because maybe the only examples you will be given for tests are one-word strings. Otherwise, maybe you may wanna add some safeguards to your code. Paste this line in your function definition:

let str = str.toLowerCase().replace(/[\W_]/g, '')

This line first takes in the string that has been passed in as an argument in examples below, lower cases all the letters and takes out non-alphanumberic characters.

Solution 1: Comparing a string with its reversed version

Since in JS the .reverse() function works only on arrays, we’ll need to:
1. Split the word into an array, saving it into a variable.
2. Reverse the array.
3. Put it back together.
4. Compare the initial string to the reversed one.

function checkPalindrome(str){
  let reversed = str.split("").reverse().join("")
  return str === reversed
}let str1 = "anna"
let str2 = "banana"
let str3 = "kayak"checkPalindrome(str1)
// -> truecheckPalindrome(str2)
// -> falsecheckPalindrome(str3)
// -> true//0.52 ms

You can make it even simpler, by using the ES6 spread feature, like here:

function checkPalindrome(str){
  let reversed = [...str].reverse().join("")
  return str === reversed

Now, this is most probably the most intuitive and straightforward solution but sadly, it is not the most efficient one.

Solution 2: Recursion

In this solution, we will use recursion (a function calling itself to see if ). Here are the steps:
1. Declare a function that accepts one argument, a string.
2. Save the string length to a variable.
3. Check if there are more letters left, if so, proceed and otherwise, you have a palindrome.
4. Now, if first and last letters are the same, invoke the function again passing the string with the first and last letters sliced. Otherwise, return false.

function checkPalindrome(str){
  let le = str.length;  if (le === 0 || le === 1) {
    return true;
  if (str[0] === str[le - 1]) {
    return checkPalindrome(str.slice(1, le - 1) );
  return false;
};//0.30 ms

Well, this is not a perfect solution because what if the string passed is an empty string or just one letter?

Solution 3: For loop

In this solution, we will again reverse a string, this time using a for loop to check if the letters are exactly the same on both sides.
1. Declare a variable with the length of the string.
2. Declare a for loop, using half of the length of the string as a reference point.
3. Check if each letter is the same as its mirror equivalent — or, a character on the other side (measured with index — 1).

function checkPalindrome(str) {
 let l = str.length;
 for (let i = 0; i < l/2; i++) {
  if (str[i] !== str[l - 1 - i]) {
   return false;
 return true;
}//0.20 ms

This solution is more efficient because we are only checking half of the letters — its computing time is approximately over 2x faster than the first solution.

Bonus: Recursion + control flow

Here is an answer suggested on StackOverflow by Jason Sebring that I found curious:

function checkPalindrome(str,i) {
  return (i=i||0)<0 || i>=str.length>>1 || str[i]==str[str.length-1-i] && checkPalindrome(str,++i);

In JavaScript control flow operators (&& and ||) function as an alternative to if/else. In this solution, we are using them in three places. Here is a step-by-step explanation:
1. Declare the function with two arguments, the string and the index: function checkPalindrome(str,i).
2. Initialize the index by composing an expression that will always evaluate to false so it will proceed to the next argument: (i=i||0)<0 .
3. Check if index is already half way but skips checking middle odd char. We use bitwise operator >> to divide by 2. If this expression is true, the check is done, if not, it proceeds to the next condition: i>=str.length>>1.
4. Compare if the mirror characters (same places on both sides) are the same. If not, exits and assumes that this expression is not a palindrome. If true, proceeds: str[i]==str[str.length-1-i].
5. Recursively call on the function to repeat the whole process: checkPalindrome(str,++i).

As with everything in JavaScript, there are many ways to solve this problem. I considered using .reduce() or .every() but it just seemed like an overkill given the fact that you can’t break the iteration, which results in low performance. I’d be curious of your takes on this common problem!

Source : Palindrome

Author: Aditya Bhuyan

I am an IT Professional with close to two decades of experience. I mostly work in open source application development and cloud technologies. I have expertise in Java, Spring and Cloud Foundry.

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s