Algorithms: Check if a String Is a Palindrome in 4 Different Ways

?A man, a plan, a canal ? Panama!? palindrome // true

Photo by Evgeny Tchebotarev from Pexels

Today, I woke up quite satisfied as I realized it?s a palindrome date: 02-02-2020.

A palindrome is a word, number, or a phrase that reads the same forwards as well as backward, 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!

Palindrome Algorithm

Welcome to my algorithm 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 by 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, you might want to 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-alphanumeric 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.

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 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 the first and last letters are the same, invoke the function again, passing the string with the first and last letters sliced. Otherwise, return false.

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).

This solution is more efficient because we are only checking half of the letters ? its computing time is approximately two times faster than the first solution.

4. Bonus: Recursion + Control Flow

Here is an answer suggested on Stack Overflow 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 the index is already halfway but skips checking the middle odd char. We use the 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, exit and assume that this expression is not a palindrome. If true, proceed: str[i]==str[str.length-1-i].
5. Recursively call on the function to repeat the whole process: checkPalindrome(str,++i).

Conclusion

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 about your takes on this common problem!