An algorithm a day: Palindrome check in JavaScript
Palindromes are words or phrases and even numbers that read the same forwards and backwards. Short palindromes are quite common such as: civic, kayak, level, madam, noon, radar, rotor, and solos. They are also found in names like Eve, Hannah, Anna, Otto and Bob.
Background
The word “palindrome” was created in the 17th century by the English playwright Ben Jonson from the Greek roots palin (πάλιν; “again”) and dromos (δρóμος; “way” or “direction”).
The Sator Square is probably the oldest palindrome known to us. A version was found on a wall in the city of Herculaneum that was buried in ash in 79 AD. This Latin palindromic square can be translated as:
“ Arepo the sower holds the wheels with care.”
What makes this a really cool palindrome is that can be read from top-to-bottom, bottom-to-top, left-to-right, and right-to-left.
Ancient Roman, Greek and Hebrew writers all loved palindromes and sprinkled them throughout their writings. Guess they really liked ‘playing’ with their words
The code
But that is enough history for now. Let’s code!
There is quite an elegant way to check if a string is a palindrome. We take our string and reverse it. If the reversed string is the same as the original string, then yes, we have a palindrome. To reverse a string, we use:
split('').reverse().join(''); For example:
function reverse (string) {
var newString = string.split('').reverse().join('');
return newString;
}reverse("marina");/// gives us "aniram"
P.S. You can also use a for loop or .reverse() to reverse an array.
The complete palindrome check function will look like this:
function checkPalindrome(str) {
return str == str.split('').reverse().join('');
}checkPalindrome("racecar"); //return true
checkPalindrome("palindrome"); //return false
checkPalindrome("1890981"); //return true
Getting into phrases
But of course that is too easy, no? All the cool palindromes are sentences or phrases and not just single words of a row of numbers. Palindromes by default ignore capital letters , punctuation and spaces. But functions do not.
Have a look at this famous palindrome:
A man, a plan, a canal: Panama.
If we were to check it in our checkPalindrome function, it will say that it is NOT a palindrome. The same for “Racecar” and “race car”.
Regex (or regexp) to the rescue!
Regular expressions use special codes to find patterns in strings of text and then do something with these patterns. In our palindromes we want all the spaces and special characters to be removed. The string itself should also be turned into lowercase.
(Regular expressions are quite a large subject and there are a lot of resources that explain them. You can read more about them in this guide.)
The regular expression that we are going to use look like this:
/[^a-z0-9]+/g[^a-z] matches the characters that is not found between a and z[^0-9] matches the characters that is not found between 0 and 9The g flag says that it should be a global search. It will look for every occurrence instead of just the first one.
Now, our palindrome check will look like this:
1. function isPalindrome(str) {
2. str = str.toLowerCase().replace(/[^a-z0-9]+/g, '');
3.
4. return str === str.split('').reverse().join('');
5. }On the second line of the function we are saying that the string should be:
a. turned into lower case characters and
b. that all the non-alphabetical and non-numerical characters should be replaced with
'' . (Which means nothing in this case.)PS. Remember that you can ONLY use .replace() with 'strings'!!
On the fourth line of the function we are checking again if the string is a palindrome. Just like we did in the checkPalindrome function.
Lets play!
Copy or write the code in your console and check if these words and sentences from rinkworks.com are indeed palindromes.
Here are a few of my favourites:
"Eva, can I stab bats in a cave?"
"Murder for a jar of red rum."
"Was it a car or a cat I saw?"
"Straw? No, too stupid a fad; I put soot on warts."Palindromes in the real world
Palindromic genetic sequences have an important role in molecular biology.
The DNA sequence AACTAGGC has a nucleotide-by-nucleotide complement that is TTGATCCG. If you reverse the order of the nucleotides in the complement string, you will get the original sequence. This ‘mirror’ sequence effect is crucial for cell replication and repair.
Recent studies have shown that large parts of the sequences of the X and Y chromosomes are palindromes. This means that these sequences can ‘self-heal’ by bending over in the middle and forming a hair-pin.
And that is the end of our palindrome journey! In the next algorithm we are going to play with encryption!!
Previous algorithms: Calculate the factorial of a number.
