Algorithms 101: How to check if a string is a palindrome
When it comes to job search and coding interviews, you will need to be able to think through algorithm-based interview problems in front of an interviewer or panel. Practicing at the very start will put you on the path to success in technical interviews.
A common question you can expect to implement is checking if a string is a palindrome. To get you familiar with this problem, we will review what an algorithm is and learn how to solve this problem in several ways.
Ace your coding interview the first time
This learning path will take you through all that you need to know to crack your JavaScript interviews with confidence, everything from Data Structures to System Design.
Algorithms refresher#
Generally speaking, an algorithm is a set of steps it takes to do something. Think about what it takes to bake a cake or change the oil in your car. All of the steps and all of the tools or ingredients needed to make those things happen in order is a part of an algorithm.
At a high level, an algorithm is a recipe or a guide on how to execute a series of steps that will solve a problem.
In computer science, algorithms refer to a sequence of well-defined instructions that tell the computer what to do to solve a problem. Just like we have to have a series of steps to bake a cake, we need a series of well-defined instructions to create an algorithm that will solve our problem.
There are all kinds of algorithms out there, and they commonly come up in coding interviews. Algorithms are applied to different data structures. So, we take a data structure and apply an algorithm to do certain operations on it.
In this article, we will look at how to manipulate a string with an algorithm, specifically, how to check if a string is a palindrome.
A Visual Introduction to Algorithms
Learn introductory computer science algorithms, including searching, sorting, recursion, and graph theory through a combination of articles, visualizations, quizzes, and coding challenges. Implement Challenges in Java, Python, C++ or Javascript.
Coding challenge breakdown#
The goal of this algorithm is to input a string and use a function to check if it is a palindrome.
A palindrome is a word or phrase that reads the same backward and forward. When palindromes are the length of a sentence, they ignore capitalization, punctuation, and word boundaries.
For example: racecar, 1001, 11/11/11, or 11:11.
Prompt#
Given a value, write a function that will test to see if the string is a palindrome or not. Return true if it is or false if it’s not.
Examples:#
isPalindrome(“”) // true
isPalindrome(1010) // false
isPalindrome(“taco Cat”) // true
isPalindrome(“Was it a car or a cat I saw?”) // true
isPalindrome(“hello”) // false
isPalindrome(“momma made me eat my m&ms”) //false
Approach#
There are several different approaches to take with this problem that we will go through below. But first, let’s talk through it as if we were just explaining the answer to someone without code.
So, we are given a value. What is that value? Is it a string?It it something else?
The prompt doesn’t indicate what the type of the value was. If you were in an interview situation, this could be a place where you would confirm with the interviewer if the given value was a string.
Since a palindrome could technically be anything, let’s take care of all types and take a look at all edge cases. In most cases, in a technical interview, you will not need to worry about the extreme edge cases, but an interviewer will notice if you speak up about it.
Write a function that will test whether or not that value is a palindrome. This should indicate that they want a boolean value (True or False).
Things we know so far:
- Our value can be a string, number, or object
- We need to return a boolean value
- A palindrome ignores case, spaces, and punctuation
Pseudocode#
First, we need to consider the type of value.
- If it is a number, we need to change it to a string to compare how it reads backwards and forwards.
- If it is an object, we need to somehow also change it to a string to do a comparison.
- If it is a string, we can forge ahead.
- If we have null or undefined, how do we handle that?
Once we have figured out the type and changed it to a string, we need to prep the string so we can read it left-to-right and right-to-left without any non-alphanumeric characters.
We need to take care to remove all the extraneous stuff. We can do this several ways, for example by iterating through the string to remove certain characters.
We also need to take care to ignore whether or not letters or uppercase or lowercase. We can do that by either making everything capitalized or everything lowercase.
Once all non-alphanumeric characters are gone, and we have our strings in one case, now our string is ready to test!
Think about the possible ways to handle this problem:
- Compare a string with its reversed version (JS Methods)
- Iterate using for loop and check to see if character on other side of string
=== - Use recursion to check the first and last letters before invoking the function again with the shortened string
JavaScript code setup#
There are several different ways to solve this problem. As long as you can explain your approach and you arrive at the correct answer, your approach is probably just fine. These are just three of the possible ways you can figure out whether or not a value passed is a palindrome or not.
No matter your approach, the setup requires that we ready the value to be tested. Let’s go ahead and do that now. This will be the same for all three solutions.
const stripNonAlphaNum = (val) => {let str;switch(typeof val) {case "number":str = val.toString();break;case "object":str = JSON.stringify(val);break;case "string":str = val;break;case "boolean":str = null;break;}if(str === null || str === undefined) {return null;}else if(str.length === 0){return "";}else {let newStr = str.toLowerCase().replace(/[\W_ ]/g, "");return newStr;}}
In this code we use the typeof on our val to create a switch statement that will assign the variable str to a string version of the value. If the val is a number, we just need to make it a string.
If it’s an object, you can stringify it by using the JSON method of the same name. If it’s a boolean, set the string to null as booleans are not palindromes
The next lines of code test to see if the string length is 0, or if the str is undefined or null. If an empty string, we want to assign the str to an empty string. Otherwise, we are going to return null.
Note: Technically an empty string is a palindrome as it reads the same backward and forward.
Finally we use a couple of JavaScript methods to make everything lowercase and to replace a search term with an empty string. This search term is a regular expression that looks for all non-alphanumeric characters, underscores, and spaces in a string.
We assign this expression to a variable called newStr and return it.
Keep the learning going.#
Prepare for your JavaScript coding interview without scrubbing through videos or documentation. Educative’s text-based courses are easy to skim and feature live coding environments, making learning quick and efficient.
Solution 1: Compare a string with its reversed version#
We are going to use the split, reverse, and join methods to test to see if the reversed version of the string is the same as the string itself.
const isPalindrome = (val) => {let str = stripNonAlphaNum(val);if(str === null) return false;return str.split('').reverse().join('') === str;}
In the first line of the function, we assign str to the what is returned from the stripNonAlphaNum() function that uses regex to take away all of the extraneous characters we don’t need and to lowercase all of the characters.
Here is a set of tests that you can use to make sure your code works properly:
console.log(isPalindrome("taco Cat")); // trueconsole.log(isPalindrome(1010)); // falseconsole.log(isPalindrome("Was it a car or a cat I saw?")); // trueconsole.log(isPalindrome({a: "b", b: "a"})); // trueconsole.log(isPalindrome(null)); // falseconsole.log(isPalindrome(false)); // falseconsole.log(isPalindrome("")); //true
Solution 2: Iterate using for loop#
In this solution, we are going to use a regular for loop to iterate through the string. On each iteration, let’s take a look at the corresponding letter that’s the same distance from the end to see if they are equal.
If we get to the center of the word and everything is equal, we have a palindrome. Else, we return false.
const isPalindrome =(val) => {let str = stripNonAlphaNum(val);if(str === null) return false;for(let i = 0; i < str.length/2; i++) {if(str[i] !== str[str.length - 1 - i]) {return false;}}return true;}
Here, we only iterate to the midpoint of the string because we are checking the other half of the string to its counterpart in the front half of the string.
A good approach when it comes to solving problems is to always check for false values. If we come to a pair of letters that don’t match, we know it’s not a palindrome and we can stop there. This is what the first line in the for loop is doing.
We are checking to see if the current character is equal to the character at the same spot from the end. If it doesn’t match, return false.
If we get through the whole for loop and the conditional inside the for loop hasn’t been triggered, that means all the characters are the same and we have a palindrome.
Solution 3: Use Recursion#
In this third and final solution, we are going to use recursion to find out if our value is a palindrome or not. Remember with recursion, we need to have a base case else we will exceed our maximum call stack size.
const isPalindrome = (val) => {let str = stripNonAlphaNum(val);if(str == null || str === undefined) return false;let length = str.length;if (length === 0 || length === 1) {return true;}if (str[0] === str[length - 1]) {return isPalindrome(str.slice(1, length - 1) );}return false;};
We start with getting our string value by invoking the function we wrote to lowercase characters and get rid of all the non-alphanumeric characters. If it passes the null test, we will check the string against our base case.
If the base case passes, it means we have checked all of our characters, and we have a palindrome.
The next conditional is where our recursion happens. We want to compare the first letter of the string to the last letter of the string.
If they are equal, we’ll return the isPalindrome() function, and pass in a copy of the string minus the first character and the last character as our argument.
The recursion will continue to happen as long as we have matching letters or until we hit our base case. If we hit our base case, our str is a palindrome, and we return true. If at any point we have characters that don’t match, we return false.
What to learn next#
Algorithms can be challenging. The more you practice, the better you will get at identifying patterns that will help you create a process for solving the problem.
As long as you understand the problem, you should be able to get to a solution with time. A first-pass solution is still a solution. It may not be the best solution, but you can always refactor to make it better.
There are still more algorithms to study to prepare for coding interviews. Your next steps are:
- Print duplicate characters from a string
- How to reverse a string
- How to find duplicate characters in a string
- Graph algorithms
Educative’s learning path Ace the JavaScript Coding Interview offers hands on practice with all of these problems and more. It’s your one-stop-shop for prepping for coding interviews.
You’ll cover everything from Data Structures to System Design, and by the time you’re done, your skills will be polished enough to impress at any company.
Happy learning!
Continue reading about algorithms#
Free Resources
