A palindrome is a word, phrase, number, or other sequences of characters that reads the same backward or forward. The word “palindrome” was first coined by the English playwright Ben Jonson in the 17th century, from the Greek roots Palin (“again”) and dromos (“way, direction”).
The comic is based on the famous palindrome: “A Man, A Plan, A Canal: Panama”, devised by Leigh Mercer, which references the construction of the Panama Canal and is the first mentioned on the Wikipedia page for palindromes at the time this comic was released. Normally capitalization, spacing, and punctuation are ignored.
In this article, I’m going to explain two approaches, first with built-in functions and second using a for loop.
Algorithm Challenge
Return true if the given string is a palindrome. Otherwise, return false.
A palindrome is a word or sentence that’s spelled the same way both forward and backward, ignoring punctuation, case, and spacing
Note. You’ll need to remove all non-alphanumeric characters (punctuation, spaces, and symbols) and turn everything lower case in order to check for palindromes.
We’ll pass strings with varying formats, such as “racecar”, “RaceCar”, and “race CAR” among others.
Provided test cases
- palindrome(“race car”) should return true
- palindrome(“not a palindrome”) should return false
- palindrome(“A man, a plan, a canal. Panama”) should return true
- palindrome(“never odd or even”) should return true
- palindrome(“nope”) should return false
- palindrome(“almostomla”) should return false
- palindrome(“My age is 0, 0 si ega ym.”) should return true
- palindrome(“1 eye for of 1 eye.”) should return false
- palindrome(“0_0 (: /-\ 🙂 0–0”) should return true
Implementation
Regular expressions are patterns used to match character combinations in strings. When the search for a match requires something more than a direct match, the pattern includes special characters.
To pass the last test case, we can use two Regular Expressions :
/[^A-Za-z0–9]/g
or
/[\W_]/g
- \W removes all non-alphanumeric characters
- \W matches any non-word character
- \W is equivalent to [^A-Za-z0–9_]
- \W matches anything that is not enclosed in the brackets
What does that mean?
[^A-Z] matches anything that is not enclosed between A and Z
[^a-z] matches anything that is not enclosed between a and z
[^0-9] matches anything that is not enclosed between 0 and 9
[^_] matches anything that does not enclose _
But in our test case, we need palindrome(“0_0 (: /-:)0–0”) to return true, which means “(: /-\ :)” has to be matched.
We now have “\W_”
We will also need to add the g flag for global search.
We finally have “/[\W_]/g”
/[\W_]/g was used for pure demonstrative purpose to show how RegExp works. /[^A-Za-z0–9]/g is the easiest RegExp to choose.
1. Check for Palindromes With Built-In Functions
For this solution, we will use several methods:
- The toLowerCase() method to return the calling string value converted to lowercase.
- The replace() method to return a new string with some or all matches of a pattern replaced by a replacement. We will use one of the RegExp we just created earlier.
- The split() method splits a String object into an array of strings by separating the string into substrings.
- The reverse() method reverses an array in place. The first array element becomes the last and the last becomes the first.
- The join() method joins all elements of an array into a string.
Step 1. Lowercase the string and use the RegExp to remove unwanted characters from it.
var re = /[\W_]/g;
var lowRegStr = str.toLowerCase().replace(re, ”);
Insights:
- Here, str.toLowerCase() is equal to “A man, a plan, a canal. Panama”.toLowerCase() which gives us a string as “a man, a plan, a canal. panama”.
- Here str.replace(/[\W_]/g, ”) is equal to “a man, a plan, a canal. panama”.replace(/[\W_]/g, ”) which gives us a string as “amanaplanacanalpanama”.
- Final value in lowRegStr at this point will be “amanaplanacanalpanama”.
Step 2. Use the same chaining methods with built-in functions from the previous article ‘Three Ways to Reverse a String in JavaScript’.
var reverseStr = lowRegStr.split("").reverse().join("");
Insights:
- lowRegStr.split(”) which is equal to “amanaplanacanalpanama”.split(”) gives the array as [“a”, “m”, “a”, “n”, “a”, “p”, “l”, “a”, “n”, “a”, “c”, “a”, “n”, “a”, “l”, “p”, “a”, “n”, “a”, “m”, “a”].
- Then, [“a”, “m”, “a”, “n”, “a”, “p”, “l”, “a”, “n”, “a”, “c”, “a”, “n”, “a”, “l”, “p”, “a”, “n”, “a”, “m”, “a”].reverse() will reverse the array and gives [“a”, “m”, “a”, “n”, “a”, “p”, “l”, “a”, “n”, “a”, “c”, “a”, “n”, “a”, “l”, “p”, “a”, “n”, “a”, “m”, “a”].
- [“a”, “m”, “a”, “n”, “a”, “p”, “l”, “a”, “n”, “a”, “c”, “a”, “n”, “a”, “l”, “p”, “a”, “n”, “a”, “m”, “a”].join(“”) will join all other word to form a sentence “amanaplanacanalpanama”
- So, “amanaplanacanalpanama”.split(”).reverse().join(”) = “amanaplanacanalpanama”.
Step 3. Check if reverseStr is strictly equals to lowRegStr and return a Boolean.
return reverseStr === lowRegStr;
2. Check for Palindromes With a FOR loop
Half-indexing (len/2) has benefits when processing large strings. We check the end from each part and divide the number of iterations inside the FOR loop by two.
Step 1. The first part is the same as earlier:
var re = /[^A-Za-z0-9]/g;
str = str.toLowerCase().replace(re, ”);
Step 2. Create the FOR loop
var len = str.length;
for (var i = 0; i < len/2; i++) {
if (str[i] !== str[len – 1 – i]) {
return false;
}
}
Here len/2 = 15.
Iteration for the same is explained in detail below.
For each iteration: i=? i<len/2 i++ if(str[i] !== str[len–1–i])?
1st iteration: 0 yes 1 if(str[0] !== str[15–1–0])? => if(“a” !== “a”)? // false
2nd iteration: 1 yes 2 if(str[1] !== str[15–1–1])? => if(“m” !== “m”)? // false
3rd iteration: 2 yes 3 if(str[2] !== str[15–1–2])? => if(“a” !== “a”)? // false
4th iteration: 3 yes 4 if(str[3] !== str[15–1–3])? => if(“n” !== “n”)? // false
5th iteration: 4 yes 5 if(str[4] !== str[15–1–4])? => if(“a” !== “a”)? // false
6th iteration: 5 yes 6 if(str[5] !== str[15–1–5])? => if(“p” !== “p”)? // false
7th iteration: 6 yes 7 if(str[6] !== str[15–1–6])?=> if(“l” !== “l”)? // false
8th iteration: 7 yes 8 if(str[7] !== str[15–1–7])? => if(“a” !== “a”)? // false
9th iteration: 8 yes 9 if(str[8] !== str[15–1–8])? => if(“n” !== “n”)? // false
10th iteration: 9 yes 10 if(str[9] !== str[15–1–9])? => if(“a” !== “a”)? // false
11th iteration: 10 yes 11 if(str[10] !== str[15–1-10])? => if(“c” !== “c”)? // false
12th iteration: 11 yes 12 if(str[11] !== str[15–1–11])? => if(“a” !== “a”)? // false
13th iteration: 12 yes 13 if(str[12] !== str[15–1–12])? => if(“n” !== “n”)? // false
14th iteration: 13 yes 14 if(str[13] !== str[15–1–13])? => if(“a” !== “a”)? // false
15th iteration: 14 yes 15 if(str[14] !== str[15–1–14])? => if(“l” !== “l”)? // false
16th iteration: 15 no
return true;
Above, are the two approaches to check for whether string is palindrome or not in javascript.
Conclusion
We have now looked at 2 different ways to check whether a given string is a palindrome. In terms of approximation of a palindrome, we see how it highly depends on what we mean by being “close” to a palindrome, and which algorithm we choose to use.
The 2 approaches I provided all agreed when something is a perfect palindrome, and when something is definitely not.
But the spectrum in between resulted in various different approximations, depending on the implementation and on our definition of “close”.
Please subscribe to our TryCatchBlog website to get the latest post like this.
Sources
- https://en.wikipedia.org/wiki/Palindrome
- https://itnext.io/11-way-to-check-for-palindromes-in-javascript-85dbfe7dfb5d
- https://www.freecodecamp.org/news/two-ways-to-check-for-palindromes-in-javascript-64fea8191fd7/
- https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array
vashikaran
I am not sure where you are getting your info, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for fantastic info I was looking for this info
for my mission.