Bonfire: Check for Palindromes Solution

We’re going to check for palindromes today for one of our Bonfire challenges. This is something I haven’t done yet. I have two solutions this time. The first relies on pre-existing methods. The second is a for loop.

Approaching the Problem

Let’s first take a look at what we’re given.

function palindrome(str) {
  // Good luck!
  return true;
}

palindrome("eye");

Simple and familiar set up by now. A basic function with a function call. I’m a particular fan of the somewhat cheeky, “Good luck!” in there. All right, first of all, a palindrome is a word or phrase that when reversed is the same as it was prior to reversal if you ignore spacing, capitalization and punctuation. For instance:

racecar = racecar
eye = eye
tacocat = tacocat

And my personal favorite because I am apparently still a thirteen year old:

abutttuba = abutttuba

On the flipside, the following words and phrases are not palindromes:

deerrun = nurreed
hockey = yekcoh

We already know that we have to evaluate whether a string is a palindrome or not, and the Bonfire gives us a clue right off the bat in the challenge description: ignoring spacing, capitalization and punctuation. Now we know that even though the function call only references the palindrome “eye”, the Bonfire is serious about us doing this right so we’re likely to be tested against palindromes with things like spaces, capitals and punctuation too. Something like this:

Degas, are we not drawn onward, no? In union, drawn onward to new eras aged?

This means we’re probably going to have to strip capitalization, punctuation and spacing from whatever the Bonfire throws at us.

Next thing we have to consider is that we need to be able to check the reversed string to its unreversed state. Believe it or not, we did something similar to this for the the Reverse a String Solution where we converted the string into an array, reversed the array, then turned it back into a string. We can do the same thing to help us check for palindromes in this scenario.

Finally, we need to return a true or false value depending on whether the string evaluates a palindrome or not. Let’s get started on the pre-existing methods solution:

Checking for Palindromes Using Existing Methods

The first thing I’m going to address is the stripping of punctuation, capitalization and spaces from the string. I’m going to do that using a couple of pre-existing methods. The first is toLowerCase() which removes capitalization by forcing all characters to be lowercase. The second is a replace() function that will remove spaces and punctuation.

toLowerCase() is pretty self explanatory, but I think I need to take a moment to comment on how we’re going to use replace(). Here’s what I’ve got at this stage:

function palindrome(str) {
  var stripStr = str.toLowerCase().replace(/\W|\s/g,'');
}

palindrome(“Degas, are we not drawn onward, no? In union, drawn onward to new eras aged?”);

With replace(), we’re going to come back to something you should have been introduced to shortly before the Bonfires; Regular Expressions. Before we get to that though, let me explain my approach. The first thing I did with this is create a local variable within the function that is meant to strip the string of capitals, spaces and punctuation to make finding the palindromes easier.

With toLowerCase() I’m achieving that by using a pre-existing method to force all capitals in whatever string I feed palindrome() to become lowercase. Then I use replace() coupled with regex to filter out spaces and special characters. Within Regex, //g is used to represent a global search. What I’m doing is executing a search for all non-word characters with \W, and searching for spaces with \s.

After that, the comma and ” is meant to replace whatever is found for special characters and spaces with–basically nothing. Not even a space. This effectively cleans up whatever string we’re going to feed palindrome() and I chose the particularly meaty one we met earlier because it has all the components the Bonfire is probably going to look for when it attempts to validate our solution. At this point in time, our string that was originally: Degas, are we not drawn onward, no? In union, drawn onward to new eras aged?

Now probably looks more like: degasarewenotdrawnonwardnoinuniondrawnonwardtonewerasaged

Next step is to actually check for the palindrome itself. There’s actually two approaches to this, the first is a fully automated one using all pre-existing methods (particularly our friends, split(), reverse() and join()), which I was going to cover, but Wulkan from wulkan.me has already done a pretty good job of that. Mine only differs slightly, but here it is:

function palindrome(str) {
  
  var stripStr = str.toLowerCase().replace(/\W|\s/g,'');
  var checkStr = stripStr.split('').reverse().join('');
  
  if (stripStr === checkStr) {
    console.log("the string is a palindrome.");
    return true;
  } else {
    console.log("the string is not a palindrome.");
    return false;
  }
}
  
palindrome("Degas, are we not drawn onward, no? In union, drawn onward to new eras aged?");

What we’re doing is first stripping the string of capitals, spaces and punctuation. Then since we now have:

degasarewenotdrawnonwardnoinuniondrawnonwardtonewerasaged

Which is still a string–and therefore, immutable, we need to reverse it to check for palindromes. Otherwise, you’re just checking the existing string against itself. So we use our good friends, split(), reverse() and join() to flip the string around. Finally, we use a simple if statement to check if stripStr and checkStr are deeply equivalent to each other. If they are, we return true. If they aren’t, we return false. You can replace the palindrome() parameter above with eye prior to validating if you wish, but the Bonfire should check the solution and issue you a pass whether you check for eye or check the above palindrome.

Checking for Palindromes With a For Loop

Let’s say you’re not really sure what those existing methods are doing and would rather step through this in a more “show your work” type of way. I’ve done a for loop solution for this, again, not sure if it’s really great, but it validated and seems to handle the Bonfire requests pretty well.

Here’s the problem I faced as I was thinking through this one myself. Despite my lofty goal of using no build-in methods, I still have no clue as to how to strip capitals, spaces and punctuation from a string without using the existing toLowerCase() and replace() methods. There are also a lot of solutions to the popular “check for palindromes” interview question online without relying on built-in methods. However, many of the solutions offered only check whole words for palindromes, not necessarily phrases. So in terms of prepping the string for a palindrome check, I started out the same:

function palindrome(str) {
var stripStr = str.toLowerCase().replace(/\W|\s/g,'');
}
palindrome("Degas, are we not drawn onward, no? In union, drawn onward to new eras aged?");

I’m still creating a stripped down string using toLowerCase() and replace() with regex, and the Bonfire specifically alludes to these two methods so for this particular approach, I assume that those two methods are OK to use in this case. From here, we can get to a palindrome check using a for loop.

function palindrome(str) {
    var stripStr = str.toLowerCase().replace(/\W|\s/g, '');
    for (i = 0; i < stripStr.length; i++) {
        if (stripStr.charAt(i) != stripStr.charAt(stripStr.length - 1 - i)) {
            console.log("the string is not a palindrome.");
            return false;
        }
    }
    console.log("the string is a palindrome.");
    return true;
}
palindrome("Degas, are we not drawn onward, no? In union, drawn onward to new eras aged?");

All right, let’s step through this one slowly. We already know stripStr is removing the special characters, spacing and capitals from the string we’re checking. Once we have that, we head into a for loop.

The for loop iterates through i which is set to continue looping until i is greater than the length of stripStr. This ensures that we check all characters within the string and iterate through each as well. Inside of the for loop, we have an if conditional that checks both ends of our string. stripStr.charAt(i) begins at the start of the string, and stripStr.charAt(stripStr.length – 1 – i begins at the end of the string. charAt() is a method that checks the character at the specified parameter. Technically, you might refer to these as pointers on either end of the string, but I’m not confident if that’s really the terminology we want to use.

Regardless, the subtraction portion at the end ensures that we move through backwards iteration as we subtract 1 each time we loop through. In other words, each iteration moves one further into the string, either right or left, as the loop iterates through stripStr’s length. As the loop moves through, we check each character to its equivalent partner on the other end.

Here is a partial step through as I understand it:

Pass 1:
i = 0
Add 1 to stripStr.charAt(beginning)
degasarewenotdrawnonwardnoinuniondrawnonwardtonewerasaged
Subtract 1 from stripStr.charAt(end)

Pass 2:
Add 1 to stripStr.charAt(beginning)
degasarewenotdrawnonwardnoinuniondrawnonwardtonewerasaged
Subtract 1 from stripStr.charAt(end)

Pass 3:
degasarewenotdrawnonwardnoinuniondrawnonwardtonewerasaged
Add 1 to stripStr.charAt(beginning)

Subtract 1 from stripStr.charAt(end)

And on and on it goes until the two pointers reach the other end and have evaluated the entire string against each other. If the entire string matches on either end all the way through, our function returns true. If, at any point, there is a discrepancy and one of the characters doesn’t match the other character on the other end, our function returns false. Plug it into the Bonfire and it will evaluate appropriately.

A Faulty Sidetrack

What I attempted prior to checking for false was checking for true where:

if (stripStr.charAt(i) === stripStr.charAt(stripStr.length - 1 - i))

This evaluates perfectly for nearly everything except for a two-middle character non-palindrome such as almostomla, where it inaccurately evaluated the s and t and returned true for palindrome. Changing the deeply equivalent to deeply false resolved this issue and I’m frankly still trying to figure out why. If you have an explanation, let me know!

Bonfire’s Added Underscore (Update: 04/24/2017)

It would appear that I had a situation with my solution where the underscores the Bonfire threw at it would cause the code not to validate. The regex wasn’t written to recognize underscores, even though \W takes care of dashes. So, a quick fix for this would be to add an underscore selection to our regex. This isn’t the prettiest thing I’ve seen, but it’ll do: /\W|\_|\s/g

That means our updated solution would look like this:

function palindrome(str) {
  
  var stripStr = str.toLowerCase().replace(/\W|\_|\s/g,'');
  var checkStr = stripStr.split('').reverse().join('');
  
  if (stripStr === checkStr) {
    console.log("the string is a palindrome.");
    return true;
  } else {
    console.log("the string is not a palindrome.");
    return false;
  }
}
  
palindrome("Degas, are we not drawn onward, no? In union, drawn onward to new eras aged?");

Shout outs to Paul and Mike in the comments for pointing this out! And a sincere apology to Paul for getting to this so, so, so much later than I really meant to.

Resources

JSPerf, Is Palindrome?
Benchmarking solutions to check for palindromes. These show you efficiency specifically related to Palindrome checking. Great if you want to browse.

JSBeautifier
I’m always annoyed every time I copy and paste my code from Bonfire or my text editor into WordPress that it inexplicably loses all its formatting. So JSBeautifier really deserves a shout out.

StackOverflow, Check in JS for Palindromes
Great resource with tons of different solutions.

Regex Tester
If you ever thought to yourself, “Gee, I get way too much sleep at night and don’t have enough stress in my life”, get into Regex. It’s all around us! Regex101 is a good tool to use to test out the regex you write to see what it will and will not select.


8 comments on “Bonfire: Check for Palindromes Solution

  1. Mark Madison on

    I really liked your solution using a regular expression. However, as you point out they’re always changing things on these bonfires so now I’m looking for a regular expression that will deal with underscores. Right now your code passes all the tests except for these two:

    palindrome(“_eye”) should return true.

    palindrome(“0_0 (: /-\ 🙂 0-0”) should return true.

    I have been searching for a regular expression that would work on these two but so far no luck.

    Thanks,

    Mark

    Reply
    • Khanh on

      Hi,
      Looks like they did change it up. And it appears Paul had this same issue back in September. I think I had written down to take a look at this when I had more time and then forgot to. So, the problem here is we need to account for the underscore that they’ve written sometime in 2015. So, Paul, if you’re still checking, this one’s for you too:

      While I’m sure there’s a more elegant way of writing this regex, the quick fix is to include the underscores in our replace method:

      var stripStr = str.toLowerCase().replace(/\W|\_|\s/g, ”);

      The addition of the bar | and \_ will tell our code to seek out underscores and replace those as well. That should validate now.

      I’m going to edit this into my solution and credit both you and Paul for bringing it up. Thanks! 🙂

      Reply
  2. Paul on

    Thank you for the reply, that makes sense to me now!
    My previous code worked perfectly or so I thought, but now I have come back to this problem, I see that the final test “0_0 (: /-\ 🙂 0-0” does not return true.
    From what I can see, it is keeping special characters in it and not removing them, the problem being the _ and the -.
    Again many thanks, I am about to start the next bonfire, look forward to your next entry.

    Reply
    • Khanh on

      Hi Paul, thanks for dropping by. .replace(/\W|\s/g,”) is a .replace() method using regex values to search and replace characters and other elements within a string in this particular case. I’m a little foggy on my regex and I just discovered something about my original code that could be better thanks to your question, so thank you! I’ll talk about it below. 🙂

      In regex, you declare //g (one / in front of the search right after the open parenthesis, and one just before g) to represent a global search. In other words, “search everything for these things inside of the slashes and replace all of them that you find”.

      Inside of //g, we declare the values we want to search and replace. In this case \W means, “find anything that isn’t a word”. This includes spaces and special characters.

      The vertical bar | represents a boolean of OR. So we’re looking for \W or \s. In this case \s seeks out all whitespace. Technically, I’m searching and weeding out spaces twice here and can probably drop \s (and you can too if you feel it’s unnecessary and want that extra efficiency bump).

      Next the comma after the regex values represents what we’re replacing anything we find using regex with. In this case, two quotes with nothing in between them. This means to replace all special characters and spaces with…well–nothing. So you get a long string that is stripped of special characters and spaces as a result.

      If you were asking why regex uses those slashes and the vertical bar exactly, I can imagine it’s so .replace() and similar methods that take regex values understands that \W is regex for “special characters and spaces” instead of just W, where it would assume you just want to replace all uppercase Ws with whatever.

      I hope I covered everything.

      Reply
  3. Paul on

    Love the blog, I am pretty new to code so here is my solution!
    function palindrome(str) {
    var strA = str.toLowerCase().replace(/\W|\s/g,”);;
    console.log(strA);
    var strB = strA.split(”);
    console.log(strB);
    var strR = strB.reverse();
    console.log(strR);
    var strR = strR.join(”);
    console.log(strR);
    if (strA === strR){
    return true;
    }else{
    return false;
    };
    };

    palindrome(“Race car”);

    I did the console log to check my code as I wrote it in CodeCademys editor.

    Reply
    • Khanh on

      Thank you for sharing your solution, Paul! It’s looking good. I always like seeing different approaches the same problem, it really demonstrates how we might all differ in our technique but we’ll all end up in the same place. 🙂

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *