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:
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:
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
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.
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
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
Step 2: Reversing the original text
Step 3: Comparing the original and the reversed text.
So, madam is a Palindrome because they are the same thing.
Handling phrases, clauses and sentences.
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.