freeCodeCamp Algorithm Challenge Guide: Check for Palindromes

freeCodeCamp Algorithm Challenge Guide: Check for Palindromes
0.0 0

#1

:triangular_flag_on_post: Remember to use Read-Search-Ask if you get stuck. Try to pair program :busts_in_silhouette: and write your own code :pencil:

:checkered_flag: Problem Explanation:

Our goal for solving this problem is tidying up the string passed in, and checking whether it is in fact a palindrome.

  • If you are unsure of what a palindrome is, it is a word or phrase that when reversed spells the same thing forwards or backwards. A simple example is mom, when you reverse the letters, it spells the same thing! Another example of a palindrome is race car. When we take out anything that is not a character it becomes racecar which is the same spelled forwards or backwards!

Once we have determined whether it is a palindrome or not we want to return either true or false based on our findings.

Relevant Links

:speech_balloon: Hint: 1

Regular expressions, RegEx, can be used to remove unwanted characters from the string.

try to solve the problem now

:speech_balloon: Hint: 2

The Array.prototype.split and Array.prototype.join methods can be of use here. For and while loops are another alternative, or why not even map!

try to solve the problem now

:speech_balloon: Hint: 3

String.prototype.toLowerCase can be used to make a string lowercase.

try to solve the problem now

Spoiler Alert!

687474703a2f2f7777772e796f75726472756d2e636f6d2f796f75726472756d2f696d616765732f323030372f31302f31302f7265645f7761726e696e675f7369676e5f322e676966.gif

Solution ahead!

:beginner: Basic Code Solution:

function palindrome(str) {
  return str.replace(/[\W_]/g, '').toLowerCase() ===
         str.replace(/[\W_]/g, '').toLowerCase().split('').reverse().join('');
}

:rocket: Run Code

Code Explanation:

  • We start by using regular expressions to replace any white space or non-alphanumeric characters with nothing (or null), which essentially removes them from the string.

  • Next we chain .toLowerCase() to remove any capital letters because A is a different character than a. The problem did not ask us to worry about making sure the case of the characters was identical, just the spelling.

  • Our next step is to take our string and .split() it, .reverse() it, and finally .join() it back together.

  • Last step is to check that the string is the same forwards and backwards and return our result!

Relevant Links

:sunflower: Intermediate Code Solution:

function palindrome(str) {
  str = str.toLowerCase().replace(/[\W_]/g, '');
  for(var i = 0, len = str.length - 1; i < len/2; i++) {
    if(str[i] !== str[len-i]) {
      return false;
    }
  }
  return true;
}

:rocket: Run Code

Code Explanation:

  • We start by using the same methods of replacing characters we don’t want in the string using RegEx's, regular expressions, and then make our string lowercase.

  • Next we set up our for loop and declare an index i to keep track of the loop. We set our escape sequence to when i is greater than the length of the string divided by two, which tells the loop to stop after the halfway point of the string. And finally we set i to increment after every loop.

  • Inside of each loop we want to check that the letter in element [i] is equal to the letter in the length of the string minus i, [str.length - i]. Each loop, the element that is checked on both sides of the string moves closer to the center until we have checked all of the letters. If at any point the letters do not match, we return false. If the loop completes successfully, it means we have a palindrome and therefore we return true!

Relevant Links

:rotating_light: Advanced Code Solution (most performant):

//this solution performs at minimum 7x better, at maximum infinitely better.
//read the explanation for the reason why. I just failed this in an interview.
function palindrome(str) {
  //assign a front and a back pointer
  let front = 0;
  let back = str.length - 1;

  //back and front pointers won't always meet in the middle, so use (back > front)
  while (back > front) {
    //increments front pointer if current character doesn't meet criteria
    while ( str[front].match(/[\W_]/) ) {
      front++;
      continue;
    }
    //decrements back pointer if current character doesn't meet criteria
    while ( str[back].match(/[\W_]/) ) {
      back--;
      continue;
    }
    //finally does the comparison on the current character
    if ( str[front].toLowerCase() !== str[back].toLowerCase() ) return false
    front++;
    back--;
  }
  
  //if the whole string has been compared without returning false, it's a palindrome!
  return true;

}

:rocket: Run Code

Code Explanation:

  • I was given this problem in an interview (spoiler: I wasn’t hired :frowning: ) I quickly arrived at the basic solution, and the interviewer told me to make it better. The algorithm would take way too long if he passed the Bible as the string. He wanted it to be instant.

  • The simpler solutions perform very poorly on long strings because they operate on the whole string multiple times (toLowerCase(), replace(), split(), reverse(), join()) before comparing the whole string twice.

  • The beauty of this solution is it never needs to read through the whole string, even once, to know that it’s not a palindrome. Why read through the whole string if you can tell that it’s not a palindrome just by looking at two letters?

  • Uses a while loop instead of a for loop as a best practice - because we are using two variables, one is the index starting from the beginning of the string, and the other starts at the end of the string.

Relevant Links

:clipboard: NOTES FOR CONTRIBUTIONS:

  • :warning: DO NOT add solutions that are similar to any existing solutions. If you think it is similar but better, then try to merge (or replace) the existing similar solution.
  • Add an explanation of your solution.
  • Categorize the solution in one of the following categories — Basic, Intermediate and Advanced. :traffic_light:
  • Please add your username only if you have added any relevant main contents. (:warning: DO NOT remove any existing usernames)

See :point_right: Wiki Challenge Solution Template for reference.


Can anyone explain Regex?
Solution Explanation please?: Check for Palindromes
#2

#3

#4

I wanted to see if I could come up with another solution than the obvious one, and so I came up with this, I take half of the word and check if its equal to the other half reversed:

function palindrome(str) {
  var chrs = str.toLowerCase().replace(/[\W_]/g, "");
  var firstHalf = chrs.substr(0,chrs.length/2);
  var secondHalf = chrs.substr(chrs.length/2);
  
  if(chrs.length % 2 === 0){
  	return firstHalf == secondHalf.split("").reverse().join("");
  } else {  	
    return firstHalf == secondHalf.substr(1).split("").reverse().join("");  	
  }
}

What do you guys think?


#5

Your code is a lot cleaner than mine, here is my answer…it’s ugly, but it works lol

// THIS FUNCTION TESTS STRINGS FOR PALINDROMES

function palindrome(str) {
  // Good luck!
  
  var res = str.toLowerCase();
  var arr = res.split("");
  var newA = [];
  var rev = [];
 
 for(var i = 0; i < arr.length; i++){
  	if( /[a-z]/i.test(arr[i]) || /\d/i.test(arr[i]) === true){
  		newA.push(arr[i]);
  		rev.push(arr[i]);
  	}
  }
	
   rev.reverse();

if (rev.toString() === newA.toString()){
	console.log('Yeah, baby!');
	return true;
} else

return false;

}

#6
// shortest readable soluton I could come up with
function palindrome(str) {
  str = str.toLowerCase().replace(/\W|_/g, "").split("");
  var reverseStr = str.slice().reverse();
  return reverseStr.join("") === str.join("");
}

#7

As a beginner I obviously came up with the solution identical to the Basic Code Solution.

Can anyone explain why the Advanced Code Solution is better than the Basic one? I don’t get it.
.split() and .join() are not used in this solution, but is not the reason, I suppose…

Thanks.


#8

I’m also interested if intermiediate and advanced solutions are somehow better and why.


#9

Because shorter code does not means better. The reverse() cost a lot.
Just try to implement the reverse by yourself and you’ll find out that you need extra space, and you’ll need to scan through the input once to swap the elements to form a reverse array. That’s just for reverse. You’ll need to scan through the input once again to compare if each element is different.

So the basic solution need extra space and 2 scans and lots of data swaps to complete the task. the cost of extra space and time to do the 2 scans grows when your input become bigger. But the intermediate solution need no extra space, no data swaps, and only need one scan.

The reason that advance solution being advance is because it uses the common algorithm technique “divide and conquer”. You solve a problem by breaking the bigger problem into smaller and easier ones, resolve them and then combine the results together.


#10

Here’s my solution which I hope is clear and easy to understand for you all.

function palindrome(str) {
  // Good luck!
  
  var rcase = str.replace(/[\W_]/g, ""); //remove all non-alphanumeric characters
  var lcase = rcase.toLowerCase(); //turn everything to lowercase
  var revcase = lcase.split("").reverse().join(""); //reverse the string to check if the reversed words match the first words.
  
  if (lcase == revcase) { //check if lcase match revcase, if yes, return true
    return true;
  } else if (lcase !== revcase) { //otherwise return false.
    return false;
  }
  
}

palindrome("eye");

#11

This took me some time, didnt understand the RegEx at first. This is my solution.

     function palindrome(str) {
     var check = str.replace(/[\W_]/g, '').toLowerCase();
      var strReverse = check.split('').reverse().join('');
     
      if(strReverse === check){
        return true;
      }else {
        return false;
      }
      
      
    }



palindrome("RACE CAR");

#12

Nice, i got the exact same, except my RegEx was:
/[^a-z0-9]*/gi


#13

Hello, I came with a different solution; For me the most difficult part was to get and understand /[W_]/g

function palindrome(str) {
  // Good luck!

  var re = /[\W_]/g;                                    
  var clean = str.replace( re ,'');
  var final = clean.toLowerCase();
                          
  var reverse = final.split('').reverse().join('');
  
  if (reverse != final) return false;
  return true;
}



palindrome("eye");


#14

Below is what worked for me. I did not see this solution listed but to me it was what made the most sense. I googled to get the regex to remove special characters but otherwise just used documentation I found online.

function palindrome(str) {
  // Good luck!
  str = str.replace(/[^a-z0-9+]+/gi, '').toLowerCase();
  revStr = str.split('').reverse().join('');
if (revStr == str) {
 return true;
} 

  return false;
}

palindrome("%booger_34!and)farty&butt");

#15

Why does it says in the challenge to get rid of all non-alphanumeric characteres, and then trying to test a string like this one “0_0 (: /-\ :slight_smile: 0-0” ??


#16

\W means non word or the reverse of \w
Now \w is the shorthand notation of [a-zA-Z0-9_]

Which means [\W] is enough to match non-words and replace with blank globally due to /g (global modifier.)

Hope that would help you to understand in easy and better way


#17

I wanted to share this because I thought it was kind of cool. I wrote it so that it read kind of like the definition of a palindrome, in that it’s a ‘sequence that reads the same backward as forward’. I just made a single for loop with an if statement that checks both ends of the string while incrementing to the middle. Pretty cool!

function palindrome(str) {
  //Good luck!
  var text = String(str.toLowerCase());
  var rep = text.replace(/[^a-z0-9+]+/gi, '');
  var textArray = rep.split('');

  for (var i = 0; i < textArray.length; i++) {
    if (textArray[i] != textArray[textArray.length - (i + 1)]) {
      return false;
    }
  }
  return true;
}

#18

So this is my function. It is a combination of google research and pure experimenting. And most importantly it works. So is it any good or is there a better way?

function palindrome(str) {
  var change = str.replace(/[\W_]/g, "").toLowerCase();
  for (var i = change.length - 1, o = ''; i >= 0; o += change[i--]) {
         }
  if(change === o){
    return true;
  }
return false;
}

palindrome("perica reze raci rep");

#19

I agree with @adigo that functions such as reverse() can hide a lot of time and space complexity and that’s why the advanced solution is better. I don’t think however that the advanced solution can be described as a divide and conquer algorithm. It’s a solid iterative algorithm that runs in O(n) time, but there is no breaking down and combining involved. All appropriate pairs of characters in the string str are simply compared to each other in a consecutive fashion.


#20

I took a different approach and ran into some trouble. After finding this page and reading and trying things, I decided my approach wasn’t great. But I wanted to stick with it and see if I could make it work. With help from the FCC chat room I found out my For loop was formatted poorly where it would Return True and quit out before trying the entire word. I made some changed to the order and removed an Else statement from inside my For loop and was able to get the challenge to complete with my initial approach.

After reading everything here, I understand that my approach is wordy and slow and that I checked the entire word and only needed to check half the word. However, since I put the time into the code, I wanted to see if my approach was salvageable, instead of just copy and pasting someone else’s answer.

Here is my code, will this approach work in all cases?

function palindrome(str) {
  str = str.replace(/[^A-Za-z0-9]/g, '');
  str = str.toLowerCase();
  str.split('');
  
  for (i = 0; i <= str.length - 1; i++) {
    if (str[i] != str[(str.length - 1) - i]) {
    return false;
   }
   
  }
  return true;
}


palindrome("almostomla");