The Ultimate Guide to JavaScript Algorithms: Palindromes

Celý článek

In this challenge we further strengthen our string manipulation skills by implementing simple algorithms to test if a string of text is a palindrome.

What is a palindrome?

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!

You should already have your development environment setup for this course. Update your cloned repository by running the command git pull. Inside the Beginner folder, navigate to the palindromeChecker folder. Our work for this challenge will be done in here. Make sure to follow along in the index-START.js file.

The Challenge

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

palindromeChecker('racecar') // will return true

Let's break down the problem, shall we?

Algorithmic Thinking

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, we'd convert text to a single case type which could be upper or lower.

Finally, we "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 number 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 we could pull off.

In this challenge, we'd consider two, yet three ways to implement this as highlighted below:

• An Intuitive Approach
• Looping Through and Comparing Characters
• Looping Through and Comparing Characters(Optimized)

An 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? Let’s see.

function palindromeChecker(text) {

    var reversedText = text.toLowerCase()
        .split('').reverse().join('')

    return text === reversedText
}

You're probably thinking "this really isn't very direct though". Oh well! Let's unveil the "mysteries".

• 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 passing in an empty string as the only argument in order to spread the characters into an 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 strengths of JavaScript. Elegant syntax!

At the end we return the result of our comparison which is a Boolean indicating whether 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.

Now that was easy, wasn't it? Let's try something slightly more complex.

Looping through and Comparing Characters

This could be a bit more confusing than the previous implementation. But we'll break it down as always, so stay strong.

In this approach, we 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 and if the string were a palindrome, all of these would test true.

Alright now! Let the code speak for itself.

function palindromeChecker(text) {
    let charArray = text.toLowerCase().split('')

    let result = charArray.every((letter, index) => {
        return letter === charArray[charArray.length - index - 1];
    })

    return result
}

Let's do the review thing!

• First, We convert all letters of the string to lowercase, then use the .split() method 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 and 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.

There's something wrong with our second implementation performance-wise. Did you notice? Can you identify the problem?

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.

If you try to perform this comparison manually on paper, you'd notice that once you loop beyond the character at the middle position, you start repeating comparisons you've already gone through in the first half of the iteration. That's redundant, don't you think?

We have to fix this!

To fix this, we'd add a check to ensure that we stop looping once we get to the mid-point of the string.

You may take a break from reading and try this out. I'd encourage you to try your hands on optimizing this.

Looping through and Comparing Characters (Optimized)

In the code snippets below, we fix this problem by using a for-loop to iterate through the string of text only up till the mid point while carrying out our usual comparison.

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

Now, let’s test our solutions.

Testing

Testing Correctness with Jest For each solution above, run the command below to start the tests:

npm run test palindromeChecker

Here are the results:

• The Intuitive Approach

• Looping through and Comparing Characters

• The Fix

Our tests passed in all cases. You deserve a glass of scotch. What brand would you like?????

Testing Performance with JSPerf Follow this link to JSPerf, to test the various solutions we’ve just considered. There, we compare the implementations we have just explored to see which performs better. See the results below:

Always try out tests on your own to ensure you have similar results. From the results of our test, we can conclude that:

The fixed loop method is the fastest implementation considered. The un-optimized loop method initially considered comes in second place and is approximately 47% slower, while the seemingly intuitive approach is the slowest of them all (87% slower).

Pretty interesting results!

Practical Application

This challenge is mostly encountered in JavaScript coding interviews however, the techniques used in string reversal and comparison of the characters come in handy in situations where you may be required to manipulate strings and arrays in real-world JavaScript applications.

Conclusion

We've now examined two yet three ways to implement a palindrome checker in JavaScript. Each implementation gets 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.

After running our performance tests, we have reached the conclusion that the most optimal solution among the three methods considered, is the method of looping through the string and comparing characters from one end with the characters in their corresponding position from the other end, while terminating the loop at the mid-point of the string.

You must never forget that the overall performance of an application is cumulatively determined by the seemingly small things . This means that the little wins like this matter a lot.

Further Reading

For further learning on some of the concepts explored in this challenge, you may use the link below:

• Array.prototype.every()

See you in the next one!✌????