A few ways to solve the Palindrome problem in JavaScript10 min read

on

I first joined freeCodeCamp over one year ago, this is a great place to start learning to code and especially, it’s free. But for a long time, I hadn’t visited this site regularly hence I’m now really excited to earn my very first certificate. Go through some challenges on freeCodeCamp, I’ve seen ‘check Palindrome‘ challenge, which is one of the most popular problems to start your coding journey. So, I write this article to solve this article in a few different ways in JavaScript.

First, let’s see the introduction of this challenge on freeCodeCamp:

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 into the same case (lower or upper case) in order to check for palindromes.

We’ll pass strings with varying formats, such as "racecar", "RaceCar", and "race CAR"among others.

We’ll also pass strings with special symbols, such as "2A3*3a2", "2A3 3a2", and 

These are the test cases:

  • palindrome("eye")should return a boolean.palindrome("eye")should return true.
  • palindrome("_eye")should return true.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.palindrome("five|\_/|four")should return false.

This problem is not really hard to solve, we just need to think a little bit before solving that. As the requirements of this problem (remove all non-alphanumeric characters) that is the reason why it’s better that we solve it with regular expression. But by traditional way, using for loop, we still could handle that 100% legit.

Method #1: Using for Loop

Now let’s make things simple. I will give you a guide with for loop first.

For example, we have a string: “abba” with a length of 4 and it’s a palindrome because “abba” == “abba”.

The idea:

When we already know the length of the string you want to check, implement a for loop (but where is a start and where is the stop?). We will break things into 2 separate parts, one for the haft first indexes and one for the last haft indexes. Loop through the first one and use if condition to check whether both are equal, then return true, false otherwise.

str = "neveroddoreven"
First index should equal the last: str[firstIndex] == str[lastIndex] (n = n);
Second index should equal the second-last: str[secondIndex] == str[secondLast] (e = e);
Third index should equal the third-last index: str[thirdIndex] == str[thirdLast] (v = v) and so on...

Pseudocode

str = "abccba"
first_half_indexes: "abc"
last_haft_indexes: "cba"
if(str[first_half_index] == str[last_haft_indexes])
   return true
else
   return false

Because “palindrome("never odd or even") should return true.” So we need to use regular expressions before we get inside the for loop, we need to remove the extra spaces first then solve this problem.

Now I am sure that you know the idea how to solve this problem, here is our code:

Let’s break down what happened with this code above:

  • On the first line, we use a regular expression to match all the things that are NOT A-Z, a-z, 0-9, [^A-Za-a0-9] means match anything except what is inside these brackets ([ ]) and after circumflex (^). Inside the brackets ([ ]) is the combination you want to search, and after circumflex is the combination that you want to don’t match. In this case, we want to match all stuff like spaces, special characters, etc…If you want to learn about regular expression, forward this link to MDN.
  • On the second line, we assign our string to a new string instead, which use toLowerCase() method to lower letters and replace() method passed in 2 arguments (first is the part we want to remove, this is from line one, and second is what we want to replace after, in this case, it’s empty string “”).
  • On the third line, we use length the method to get the length of the string after we convert it to a new one, see line 2.
  • On the fourth line, we implement a for loop, which loops through the first half of this string and increases each iteration by one.
  • On the fifth line, we check whether it satisfies the condition or not, str[i] are the indexes of first half string, and str[len - i - 1] are the indexes of last ones. We need to – 1 because the last element of this string is str[str.length - 1] not str[str.length] and we minus i because it will just go over the last half of this string. If any of those not satisfy the condition, we return false, otherwise true.
/* Here len/2 = 7 ("neveroddoreven".length/2) after we remove the extra space.
For each iteration:
  ************** i = ?    i < len/2    i++    if(str[i] !== str[len - 1 - i])?
      1st iteration:        0        yes         1     if(str[0] !== str[14 - 1 - 0])? => if("n"  !==  "n")? // false
      2nd iteration:        1        yes         2     if(str[1] !== str[14 - 1 - 1])? => if("e"  !==  "e")? // false      
      3rd iteration:        2        yes         3     if(str[2] !== str[14 - 1 - 2])? => if("v"  !==  "v")? // false  
      4th iteration:        3        yes         4     if(str[3] !== str[14 - 1 - 3])? => if("e"  !==  "e")? // false  
      5th iteration:        4        yes         5     if(str[4] !== str[14 - 1 - 4])? => if("r"  !==  "r")? // false
      6th iteration:        5        yes         6     if(str[5] !== str[14 - 1 - 5])? => if("o"  !==  "o")? // false
      7th iteration:        6        yes         7     if(str[6] !== str[14 - 1 - 6])? => if("d"  !==  "d")? // false
      8th iteration:        7        no        
      Break the loop.

palindrome("never odd or even"); // Expected output: True

Method #2: Using regular expression

So, it’s done for for loop, now let us move on solve this problem with regular expression. Actually this way it has a little more prerequisites:

If you know all of it. This problem just is a piece of cake now.

Let’s break down what happened:

  • First, likewise using for loop, we need a variable call “re” to match everything that not is A-Z, a-z, 0-9 and replace those with an empty string and make it lowers.
  • Because it’s truthy if the original string is equal to the reverse string, so we create a new variable to do that. First, we need to convert this string into an array, because reverse() method doesn’t work with string. That is when split() method comes in handy. When string is converted to an array, then we reverse this string by using reverse() method and finally we use join() method to turn this array back to the string.
  • If the reverse string equals to the original string, then return true. Otherwise false.
str.split(" ") = "neveroddoreven".split(" ") = ["n", "e", "v", "e", "r", "o", "d", "d", "o", "r", "e", "v", "e", "n"];

str.reverse() = ["n", "e", "v", "e", "r", "o", "d", "d", "o", "r", "e", "v", "e", "n"]; // it's still the same because it's a palindrome.

str.join(" ") = "neveroddoreven"; // turn it back to string after reversing.
lowerStr === reverseStr // true 
"neveroddoreven" === "neveroddoreven"

Method #3: Using Stack

We know that palindrome is a word or number, which reads the same backward as forward, such as madam. We just need to check whether the reverse order of this word is the same as this word and we are done, we could finish this job by 2 methods above, but we also can use a data structure called Stack to solve this problem. Stack is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle, think about stack as the stack of books, the last book you put on the top of the stack would be the first book you take off in the stack. Stack is based on 2 operations which are push – put the newest element to the top of the stack and pop – which removes the most recently added element that was not yet removed. We can simply implement Stack in JavaScript with an array which holding elements (in our case is a string that we want to check whether it’s palindrome or not) and 2 methods push and pop which operate the same way as 2 main operations in Stack to add and remove the element.

Now let’s solve the Palindrome problem using Stack in JavaScript.

First, let’s create a function that accepts one parameter, which is a string we want to check if it’s a palindrome, inside this function, we declare 2 variables, one variable named letters which works as a Stack, and a variable named reverseWord which is a string that holds the reversed string of the primary string, but we leave it as an empty string now:

const palindrome = string => {
    let letters = [];
    let reverseWord = "";
}

Then, we loop through the string and push each of its letters to the variable letters, by doing so, we now have an array with each element represents a letter of the string, push method in JavaScript adds one or more elements to the end of an array:

for (let i = 0; i < string.length; i++) {
        letters.push(string[i]);
}

Now after we have the array with a list of characters, subsequently we need the reversed string from the primary string, which could be done easily using pop method in JavaScript, which removes the last element from an array and returns that element, because each time the pop method just pop one element and return this element, then we need to loop through the letters array and add the reverse letters to the variable named reverseWord:

for (let i = 0; i < string.length; i++) {
        reverseWord += letters.pop();
}

Almost done, now we already have the string we want to check and its reversed string, we compare those 2 strings if those are equal or not, return true or false respectively and the job is done:

if (reverseWord == string) {
    return true;
}
return false;

Put all of pieces together, we have a function that check palindrome by using Stack:

const palindrome = string => {
    let letters = [];
    let reverseWord = "";
    for (let i = 0; i < string.length; i++) {
        letters.push(string[i]);
    }
    for (let i = 0; i < string.length; i++) {
        reverseWord += letters.pop();
    }
    if (reverseWord == string) {
        return true;
    }
    return false;
}
console.log(palindrome("aca")) // true
console.log(palindrome("race")) // false

Conclusion

We’ve learned how to check palindrome using for loop and regular expression at the same time and applied some array methods to solve this problem if you have any further questions or recommendations about topics and articles I should write, just reply below, every comment is welcomed. Once again, happy coding!

Tags:

Previous Article
Next Article
Every support is much appreciated ❤️

Buy Me a Coffee