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.