hedgehog lab Dev Challenge: String Palindrome Check — JavaScript Solution

At the start of 2019 a weekly or fortnightly ‘dev challenge’ was introduced here at hedgehog lab.

This week’s developer challenge was thankfully much simpler than last week’s. This week we had to analyse a string and decipher whether or not it was a palindrome.

This is the information we were given at the start of the challenge;

Given a string (which can contain white space and punctuation characters‚ but these should be ignored)‚ write a function to check if that string is a palindrome.

Example
‘A car‚ a man‚ a maraca’ would return true
‘Adam is the best’ would return false
‘A but tuba’ would return true
‘I can say but tuba with a straight face’ would return false

A palindrome is defined as;

a word‚ phrase‚ or sequence that reads the same backwards as forwards‚ e.g. madam or nurses run.

So‚ to put it simply we need to take any given string and establish — ignoring white space and punctuation — whether it reads the same forwards as it does backwards.

There are actually multiple ways this can be achieved‚ so we’re going to look at a few possible solutions for this one. So what do we know from the information given to us?

• We know that we need to accommodate for potential white space & punctuation‚ which means we need to sanitise the string before we do anything else
• We know we need to check to see if the string is read the same forwards and backwards

So‚ let’s start by sanitising our string. The easiest way to do this is by using a regular expression to clean out everything that isn’t an alphabetical character‚ which will look something like this;

checkPalindrome(string) {
    const sanitisedString = string.replace(/[^a-zA-Z]+/g‚ '');
}

Essentially what’s happening there is the string gets looped though character by character and every character that isn’t a letter will be replaced with an empty string.

If our original string was ‘H-an nAh.’ then once passed through our function‚ our variable sanitisedString would equal ‘HannAh’

We now have another issue though‚ in JavaScript ‘a’ does not equal ‘A’‚ so if we ran ‘a’ === ‘A’ it would return false — so our above sanitisedString (HannAh) wouldn’t be counted as a palindrome even though we know that it is. So that means we need to make the letters of our string all the same case‚ which will look something like this;

checkPalindrome(string) {
    const sanitisedString = string.replace(/[^a-zA-Z]+/g‚ '').toLowerCase();
}

So now if our original string was ‘H-an nAh.’ once it’s passed through our function sanitisedString would equal ‘hannah’

Great — that’s the first part of this problem solved. We have a sanitised string which has ignored all white space and punctuation‚ now we just need to check whether or not it’s a palindrome.

The easiest way to do this is to create a second string‚ which is the sanitisedString reversed and then compare the two‚ if they match — then it’s a palindrome‚ if they don’t then it’s not. This makes our function look like this;

checkPalindrome(string) {
    const sanitisedString = string.replace(/[^a-zA-Z]+/g‚ '').toLowerCase();

    const reversedSanitisedString = sanitisedString.split('').reverse().join('');

    if (sanitisedString === reversedSanitisedString) {
        return true;
    }

    return false;
}

For context‚ the logic to get the reversed string works as follows; we split the string at each letter split('')‚ then we need to reverse it (obviously..) reverse()‚ and then we join each letter back together again join('').

I’ll demonstrate this with a non-palindromic string as it will be clearer that way;

sanitisedString === 'test';
sanitisedString.split('') === ['t'‚ 'e'‚ 's'‚ 't'];
sanitisedString.split('').reverse() === ['t'‚ 's'‚ 'e'‚ 't'];
sanitisedString.split('').reverse().join('') === 'tset';

You can pass any value into split & join functions‚ in this instance we’re passing in nothing because we don’t need to‚ we just want to separate letter by letter and join it back together‚ but you could split by the letter ‘e’ and you would get the following result;

sanitisedString.split('e') === ['t'‚ 'st'];

You can also join with anything so if you wanted to join using the letter a you could do as follows;

sanitisedString.split('e').join('a') === 'tast';

Back to our problem; as you can see‚ it’s a much simpler solution than our Fibonacci Stairs problem last week‚ but as I said earlier there are a couple of ways of doing this‚ so let’s back track a bit.

We still want to sanitise our string and make it all lowercase — so that part of the solution remains the same.

However we can choose to loop through the letters in our string‚ instead of reversing it‚ and we still get the same result. In terms of code we want something that looks like this;

checkPalindrome(string) {
    const sanitisedString = string.replace(/[^a-zA-Z]+/g‚ '').toLowerCase();

    const stringArray = [...sanitisedString];

    stringArray.every((letter‚ i) => {
        if (stringArray[i] !== stringArray[stringArray.length - 1 - i]) {
            return false;
        }

        return true;
    });
}

Let’s break down the new parts of the code‚ we want the letters in our string to become an array so that we can loop through them‚ so instead of ‘hannah’‚ we get [‘h’‚ ‘a’‚ ‘n’‚ ‘n’‚ ‘a’‚ ‘h’] — you could also do this using the sanitisedString.split() which we discussed earlier.

Once we have an array we can start our loop. We can’t use the classic forEach loop in this scenario because it will continue to loop even once it’s hit return false; which will give us false positives as long as the last instance of the loop is true. So‚ eyete would return as a palindrome even though it’s clearly not.

The logic of the loop when you break it down is fairly simple. The irepresents the index of the array which we want to check. i will start at 0 (JavaScript arrays are always indexed from 0‚ so in our example stringArray[0] will equal ‘h’ — the first letter in ‘hannah’). With each iteration of the loop‚ i will increase by 1 until we reach the end of the array.

So in our if checker the first half represents our current letter in the loop stringArray[i]. The second half needs to represent the corresponding letter that we want to check it against‚ so if we’re on the first loop‚ we want to compare it to the last letter in the array.

Remember we said that Javascript arrays are indexed at 0‚ that means with an array of 6 letters‚ the maximum index value would equal 5‚ so to find our corresponding letter‚ we must always start by taking 1 from the length of the array‚ so that we never try and check against an index which doesn’t exist — stringArray[stringArray.length — 1]. We then need to take from that the current index‚ so that our loop works backwards from the end‚ to establish the corresponding letter against the one which we are checking.

Let’s assume that we’re checking against index value 1 (the second letter in our string)‚ that would make our if check look like this;

if (stringArray[1] !== stringArray[stringArray.length - 1 - 1])

With our string ‘hannah’‚ that breaks down further to look like this;

if (stringArray[1] !== stringArray[6 - 1 - 1])

Which is;

if (stringArray[1] !== stringArray[4])

So stringArray[1] will be ‘a’‚ and stringArray[4] (the 5th letter) will also be ‘a’.

In this instance‚ a does equal a‚ so the if check will be missed‚ and on this loop we will return true‚ if at any point the if check does match‚ we return false and the loop will end and we know it’s not palindromic.

There are other ways of doing this‚ such as double ended queues‚ so these are just two examples of tackling this problem using JavaScript.

Bonus Points: No string manipulation!

If we want to be really clever about it‚ we can sanitise our string without using a regex or the .toLowerCase() part of the process.

We still need to get to our sanitised string so we’re going to use each character’scharCode to do this. Each alphanumeric character has a correlating ASCII value‚ so for example a = 97‚ b = 98‚ and c = 99. And each capital letter also has a code‚ which is always 32 less than it’s lowercase equivalent. So A = 65‚ B = 66‚ and C = 67.

We can use this knowledge to sanitise our string‚ so this would make our sanitising process look like this;

const sanitisedString = [...string].map((char) => {
    const code = char.charCodeAt(0);

    if (code >= 97 && code <= 122) {
        return char;
    }

    if (code >= 55 && code <= 90) {
        return String.fromCharCode(code + 32);
    }
}).join('');

Step by step this works as follows;

We need to change our string to an array like we did earlier‚ which is the [...string] part of our function.

We then need to loop through our filteredString and check them against our ASCII values as discussed above. We get the code for each character‚ if it’s equal to or greater than 97 (a)‚ and less than or equal to 122 (z) then it’s a lowercase letter‚ not white space or punctuation‚ so we can go ahead and add that to our sanitised string.

If the character code is greater than or equal to 55 (A)‚ and less than or equal to 90 (Z) then we know it’s an uppercase letter‚ so we add 32 to that code to get the lowercase equivalent and go ahead and add that letter to our string.

We then join our string together‚ and get our fully sanitised string.

Following this logic if our original string was ‘Ha‚N nAh!’ our sanitised string would end up as ‘hannah’. From here‚ we can then either reverse the string and compare‚ as in our first solution to this challenge‚ or we could use the loop in our second solution and check whether we have a palindrome or not.

Stay tuned for next week’s challenge: Two Dimensional Arrays!