11 ways to check for palindromes in JavaScript
The challenge
Write a function that — given a string — returns true if the string is a palindrome or false otherwise.
This is a question that often shows up in job interviews and code challenges, JavaScript being no exception.
In this article, I’m going to cover 8 different ways to solve this algorithm challenge and talk a bit about performance and pros/cons of each.
Additionally, I’ll cover 3 ways to approximate how “close” a string is to being a palindrome — 100% being a perfect palindrome and 0% being as far from a palindrome as can be.
The definition
Alright, first let’s get the definition of a palindrome straight.
A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as taco cat or madam or racecar or the number 10801.
Sentence-length palindromes may be written when allowances are made for adjustments to capital letters, punctuation, and word dividers, such as “A man, a plan, a canal, Panama!”, “Was it a car or a cat I saw?” or “No ‘x’ in Nixon”.
- Wikipedia
Setup
According to the definition, we need to strip potential non-alphanumeric characters thus convert to lower-case.
So in all of the following solutions, we will be using this clean function to get a clean sequence of characters
Each of these solutions is performance tested against 3 cases:
- A small palindrome of 10 characters
- A medium palindrome of 1000 characters
- A large palindrome of 5000 characters
The tests are run in a NodeJS process using performance.now()
1. Using a for loop
Let’s start with a very straight forward approach.
The solution is to iterate through the characters using a for loop.
For each character at position i, we compare with the character at position i from the end.
If any of these does not equal, we can reject the input as being a palindrome and break out of the loop and return false.
We also only need to iterate through the half of the string, since going through the whole string would be comparing every character twice.
Therefore, we ensure to only do string.length / 2 total iterations.
Performance:
Small: 0.0731 ms
Medium: 0.1267 ms
Large: 0.6272 ms
Pros
Performs very well, even on large strings.
We are able to return as soon as we identify the first violation.
Cons
In the world of ES6 and Bable, for loops aren't the most used anymore, and this solution appears a bit “clumsy” to read.
2. Using for…of
This method is similar to the previous, but instead of using a regular for loop, we are using for…of
With this approach, we convert the string into an array and then we iterate through each element.
For each element, we remove the last element of the array using pop() and then we compare the current element with that.
Again, if any of these does not equal, it’s not a palindrome, and we break out and return false.
Since we reduce the array as we iterate, using mutation, we still only do string.length / 2 total iterations.
Performance:
Small: 0.0415 ms
Medium: 0.0966 ms
Large: 0.9997 ms
Pros
Performs good, and looks fairly readable.
We are able to return as soon as we identify the first violation.
Cons
We imperatively mutate the array, which cost us a bit of performance.
3. Using split, reverse and join
Alright, let’s turn to use some of JavaScripts inbuilt methods.
This solution is very intuitive — we will simply reverse the string and compare it to the original. If they are equal, it’s a palindrome.
With this solution we are using the inbuilt methods split() which will split a string into an array, reverse() which will reverse the order of an array and join which will concatenate the elements of the array back together as a string.
Performance:
Small: 0.1633 ms
Medium: 0.1986 ms
Large: 1.5192 ms
Pros
Concise and very readable.
Easy to understand what is going on.
Cons
Not the most well-performing, namely on small strings.
4. Using forEach
This solution is quite similar to solutions 1 and 2.
We are going to convert the string into an array and then apply forEach on it.
For each iteration, we are doing the same comparison as in solution 1, but this time we will flag a variable isPalindrome from the outer scope, if there is a violation.
Performance:
Small: 0.0444 ms
Medium: 0.1487 ms
Large: 1.2537 ms
Pros
Plus points for using ES6 methods.
Overall more readable and easy to understand.
Cons
With forEach we cannot break the iteration, nor can we ensure only doing string.length / 2 total iterations.
This cost us a bit of performance.
5. Using map
This solution is a little different.
Again we are going to convert the string into an array, but this time we apply map on it.
Using map, we return a new array with a true or false for each element, representing whether this character matches the same character from the end.
Finally, we are using some to check if the new array contains a false.
If it doesn’t the string is a palindrome, otherwise not.
Info: some() will take a predicate function and test it on all elements in the array.
If one or more elements fail the test, some() returns false. Otherwise true.
Performance:
Small: 0.0644 ms
Medium: 0.1560 ms
Large: 0.9630 ms
Pros
Plus points for using ES6 methods.
Cons
With map we cannot break the iteration, nor can we ensure only doing string.length / 2 total iterations.
Additionally, we have to create a new list which cost extra memory, and we have to iterate through this new list — potentially — one whole extra time.
This cost us a bit of performance.
6. Using reduce
This solution is similar to using forEach, instead, we use reduce.
The key difference here is, that where we had to flag a variable in the outer scope using forEach, we can pass this flag into the next iteration using reduce.
This allows us to return the result of reduce directly.
Performance:
Small: 0.0425 ms
Medium: 0.1830 ms
Large: 0.8459 ms
Pros
Plus points for using ES6 methods.
Cons
With reduce we cannot break the iteration, nor can we ensure only doing string.length / 2 total iterations.
If the check fails early, we keep passing on false to the next iteration.
This may seem like quite a waste, namely on larger strings.
7. Using every
This approach is actually my personal favorite for checking for palindromes.
We convert the string into an array, and then we apply every to it.
Info: every() will take a predicate function and test it on all elements in the array.
As soon as a single test fails, every() immediately returns false.
Performance:
Small: 0.0414 ms
Medium: 0.1977 ms
Large: 1.4204 ms
Pros
Very concise and easy to read.
Will break early if a character does not match.
Cons
We can’t ensure only doing string.length / 2 total iterations.
In the case of a palindrome, every will continue to iterate through the whole array.
8. Using recursion
Finally, let’s solve this problem by using recursion.
The idea is to compare the first and the last character of a string.
If they are equal, we are going to create a substring where the first and last letter is removed, and again apply this to our recursive function until we either hit a mismatch, or we get to an empty string (or a string of length 1).
Performance:
Small: 0.0842 ms
Medium: 5.1806 ms
Large: 108.5716 ms
Pros
The interviewer may give you credit for knowing how to handle recursion.
Other than that, there is probably not much good to say about this solution.
Cons
There are, on the other hand, some considerations here.
We are opening a lot of function closures, and a building up a — potentially — large call stack.
Notice how the performance on the large string blows through the roof here, compared to any of the previous solutions.
Now, let’s imagine that the interviewer asks you if there is a way that we can approximate how “close” a given string is to be a palindrome.
The first question that should arise here is: What does “close” mean?
Close in terms of matches in the correct position?
Close in terms of how many letters we would have to swap to get to a palindrome?
Close in terms of how far apart the mismatching letters are from each other in the alphabet?
Close in terms of something totally different? — There are many ways this can be interpreted.
Here, I will cover 3 approaches on how to solve this problem.
I will use the following test-strings for verification.
Calculating the match percentage
Remember how we used map to create a list of true/false values representing whether a character on a given position was matching the corresponding character from the other end?
Instead of using some to check if there are any false values in the list, we can count the number of false values using filter.
Now we can divide the total length of the string with this number, and get the match percentage.
Result:
100.00%
80.95%
27.27%
0.00%
0.00%
Performance:
Small: 0.0718 ms
Medium: 0.2233 ms
Large: 1.4426 ms
Using cosine similarity
This approach is a bit more advanced.
The idea is, that we are going to split the string into two equal parts and then revert one of them.
Then we convert them into their vector representation in n dimensions, n being the length of the half strings.
Then we are going to measure the angle between these vectors.
The bigger the angle, the bigger the mismatch between the strings.
Let’s go through this algorithm step by step.
Split the string into two even half strings
(If they are not even, we can take the middle character away)
Reverse the second half
Reverse the second half string using split, reverse and join.
Convert both half strings into vectors
The tricky part here is to find a good way of representing a character as a number that includes both the character itself and its position in the string.
With this approach, I’m using the characters charCode (subtracting 96 such that ‘a’ becomes 1, ‘b’ becomes 2, etc.), and then subtracting the position in the array from that number.
The reason that I’m subtracting 96 is, that ‘a’ is the 97th character in the ASCII Table.
Calculate the dot product of the two vectors
We can calculate the dot product using the following formula
Calculate the magnitude of each vector
We can calculate the magnitude of each vector using the following formula
Calculate the cosine of the angle between the vectors
Now, let’s calculate the cosine of the angle between the vectors using the following formula
Convert into percentage
Since the cosine of the angle is in the range of [-1; 1], we want to convert this into a percentage, where -1 represents 0% and 1 represents 100%.
We simply add 1 to the cosine and divide it by to, and finally multiplies with 100.
By using this approach, we can approximate how similar the two half strings are.
Since we are using the charCode as a variable, the distance between the mismatching characters in the alphabet is taken into account here.
If the algorithm returns 100%, we have a perfect palindrome.
Result:
100.00%
90.04%
57.90%
69.17%
12.37%
Performance:
Small: 0.0314 ms
Medium: 0.2597 ms
Large: 1.5066 ms
Using Levenshtein distance
This approach is also a bit more advanced, and we will need to use a bit of mathematics.
Just as with the previous approach, we are going to start by splitting the string up into two half strings and revert the second one.
Now, the idea is to calculate the Levenshtein distance between these two strings and convert that into a measure of percentage.
The Levenshtein distance is the minimum number of single-character edits required to change one word into the other.
We can calculate the Levenshtein distance using the following formula
A single-character edit can be either an insertion, a substitution or a deletion.
For example, if we calculate the Levenshtein distance of the two words “HONDA” and “HYUNDAI”, we get 3.
We need to delete the letter “Y”, substitute the letter “O” with a “U”, and insert an “I” which is 3 edits in total.
Let’s go through this setup, and see how we can use this to approximate a string in terms of a palindrome.
Split the string into two even half strings
(If they are not even, we can take the middle character away)
Reverse the second half
Reverse the second half string using split, reverse and join.
Create a matrix
We are going to create a matrix of the size n ‧ n, where n is the size of the half string length.
Fill the matrix
We are going to fill this matrix from the upper left corner.
Count edits
We traverse through the matrix and count the edits that we are required to make.
Each “jump” in a horizontal and vertical direction will be counted as a deletion and an insertion, respectively.
Convert into percentage
Finally, we will convert this into a percentage.
This last step is easy — we simply divide the length of the half strings with the Levenshtein distance. Now we get the “inverted” percentage, so we need to subtract the result from 1. Lastly, we multiply by 100.
Result:
100.00%
80.00%
27.27%
6.67%
0.00%
Performance:
Small: 0.0635 ms
Medium: 32.5343 ms
Large: 616.9648 ms
Conclusion
We have now looked at 8 different ways to check whether a given string is a palindrome and 3 different ways to approximate how close a given string is to be a palindrome.
In terms of performance, the best way to check for a palindrome is to use either a classic for loop or a for…of loop.
In terms of readability, it’s down to preference.
My preferred is solution 7 using every.
Solution 3 is also very clean and nice.
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 3 approaches I provided all agreed when something is a perfect palindrome, and when something is definitely not.
But the spectrum in between resulted in varies different approximations, depending on the implementation and on our definition of “close”.
Thank you for reading!
If you liked this article, give the clap 👏 button a couple of hits!
If you like to learn more about how to use JavaScript to the fullest, check out my other article: JavaScript Wizard: Tips & Tricks
You can also follow me on Twitter, where I’ll be posting more content similar to this.
