How to Understand Palindrome Checker Algorithm

How to Understand Palindrome Checker Algorithm

Welcome to this tutorial, in the tutorial, we're going to build a program to check whether a text is a Palindrome or not. We will break down its algorithms step by step for you to understand the thinking behind it. So, what is a Palindrome?

You can watch it's video version:Palindrome Checker Algorithm with Javascript

What is a Palindrome?

A palindrome is a word, phrase, clause or sentence that reads the same when we reverse or when it is read from the end. This means reading it from the beginning or the end of the text gives us the same thing. Then, how do we think about Palindrome?

Thinking about a Palindrome?

There are two major ways human beings think about Palindrome.

First, we pick a letter from the beginning and the end of a text and check whether they are the same. If they're the same, then we check the next letters from both sides. If all of the characters are the same, the text is a Palindrome, but it is not a Palindrome if one or more of the characters in the text are not the same.

This is what I meant:

Original  version.PNG

Let's say we have the word "madam" and we want to check whether it is a Palindrome or not. We will group all the letters in the word into 3 sides as below:

Left: ma

Center: d

Right: ma

Step 1: comparing the first character by the left and the right

madam first and last characters.PNG

The above groupings mean that we pick the first character "m" from the left of "madam" and we compared it with the last character by the right of "madam" which is also m. Since both of them are Ms, it is possible for the text to be a Palindrome, so we move to the next comparison but if they are not equal; the text is not a Palindrome and we stop the operation.

Step 2: Comparing the second character by the left and the right.

second from the start and end.PNG

We compare the second character by the left and right of the word "madam". Since both are "As", then we move to the next comparison.

Step 3: Comparing the third character by the left and the right

center from both sides.PNG

We compare the third character by the left and right of the word "madam". Since both are "Ds" and there is nothing else to compare, then we conclude that the text is a Palindrome. You can see that "d" is at the centre and is common to both sides of the comparison.

Below is the code to achieve all we described above using JavaScript:

// it is should be in a loop
if (text[index] !== text[textLength - index]) {
  //code here
}

Another thinking behind a Palindrome Algorithm

Another way to think about a Palindrome is to take the original text ( madam for example), reverse it and compare the original and the reversed versions to see if they are the same. If they are the same; then, the text is a Palindrome, if not, it is not a Palindrome.

Step 1: Taking the original text

Original  version.PNG

Step 2: Reversing the original text

Reversed version.PNG

Step 3: Comparing the original and the reversed text.

comparing origian and reversed.PNG

So, madam is a Palindrome because they are the same thing.

Handling phrases, clauses and sentences.

removing characters.PNG

The thinking behind Palindrome becomes a bit different once we have to deal with phrases, clauses and sentences.

For example, the phrase "nurses run" is a Palindrome to human beings because it reads the same when it is reversed but it doesn't read the same to a computer when it is reversed.

Original: nurses run

Reversed: nur sesrun

The comparison will be wrong because an empty space, hyphen or underscore is a character to the computer, so the fourth character by the beginning and the end of the phrase will not be equal -- one is an "s" and the other is an empty space.

However, to human beings, the phrase is a Palindrome. So, what are we going to do? We will remove all non-alphanumeric characters from the text before we check whether it is a Palindrome or not to avoid the issue.

The code below is to remove non-alphanumeric characters using JavaScript and Regex:

let nonAlphaNumericCharacter = /[^A-Za-z0-9]/g;
text = text.toLowerCase().replace(nonAlphaNumericCharacter, '');

Now that will understand the thinking behind it, let's covert everything to code. Yeah!

function isPalindrome (text) {

  let nonAlphaNumericCharacter = /[^A-Za-z0-9]/g;
  text = text.toLowerCase().replace(nonAlphaNumericCharacter,'');
  const textLength = text.length - 1;

  for(let index = 0; index < textLength/2; index++) {
    if (text[index] !== text[textLength - index]) {
      console.log("It is not palindrome");
      return false;
    }
  }
  console.log("It is a palindrome");
  return true;
}

Let's break the code down step by step:

Step 1: remove non-alphanumeric characters and convert text to lower case

let nonAlphaNumericCharacter = /[^A-Za-z0-9]/g;
text = text.toLowerCase().replace(nonAlphaNumericCharacter,'');

Step 2: Get the number of characters in the text

const textLength = text.length - 1;

Step 3: Compare characters from the beginning and the end repetitively

  for(let index = 0; index < textLength/2; index++) {
    if (text[index] !== text[textLength - index]) {
      console.log("It is not palindrome");
      return false;
    }
  }

Since we are comparing two characters from both sides of a text, it means the total iteration will be half of the total number of the characters in a given text, and that is why we divide textLength by 2 to make sure our operation is not more than that.

if (text[index] !== text[textLength - index]) {
      console.log("It is not palindrome");
      return false;
}

The code above picks a character each from the left and the right of a given text and compares them to check if they are the same or not. We use the index to move from one character at the beginning or the end of a text to the next characters on both sides.

  console.log("It is a palindrome");
  return true;

If the for-loop runs successfully, the text is a Palindrome; so we console.log that it is a Palindrome and return true to show that it is a Palindrome.

Conclusion

Understanding the thinking behind an algorithm helps in applying it appropriately. Now, with your understanding, is the time to apply your understanding by using it to build a simple project on your own. Don't forget, "a true Roman never surrenders". See you another time.