LeetCode Valid Palindrome

Another week, another select LeetCode challenge! These challenge instructions stated to create a function that takes in a string and determines if it’s an palindrome, a word that is the same frontwards and backwards (ex. racecar). This string will consider only alphanumeric characters and ignore uppercase letters. Under these instructions, a sentence like “A man, a plan, a canal: Panama” should be checked as “amanaplanacanalpanama”.

The best way to get rid of everything in the string that isn’t alphanumeric is to use a regular expression inside the JavaScript replace method. Regular expressions can be incredibly confusing, but luckily the expression in this instance is fairly simple to read. I knew I wanted to keep all lowercase letters and all numbers, which are shown as a-z and 0–9 in RegEx. To replace every instance of an invalid character in the string, I had to add ‘g’ to the end of the expression. If the ‘g’ wasn’t present, the replace method would only replace the first instance of an invalid character. Finally, the most important part of the expression is ‘^’, which tells the expression that you’re looking for everything except the characters listed in the expression. The second argument in the replace method should be an empty string, which will remove the character in question.

Regular Expression as used in a replace method

My initial impulse when reading the instructions was that I would have to loop through the initial string to take each individual letter in the string and place it at the front. The best way to do this, I think, would be to set a new variable as an empty array, then as each iteration of the loop runs, use the unshift JavaScript method to place each letter reversed in the array.

Initial for loop

Once the loop is finished, I’d have to take the array, use the join method to combine that array into a string, and check if that new string is the same as the passed in string. If those two strings are the same, the function should return true. If they aren’t, the function should return false.

First solution

We have a successful function! Let’s check the runtime.

Pretty bad runtime

Not great! LeetCode’s runtime graph only goes up to 200 ms, so this function’s 548 millisecond time is off the charts right now. I’m not completely positive as to why it’s so high, but I believe it has to do with the for loop in the function. Iteration is an O(n) operation, but since unshift is placing a new element on the front of the solution array at every iteration, that method is iterating through the array again to update the index on every element as well. When the array gets larger and larger, the run time goes up and up and up until it hits 548 milliseconds.

One way to fix this problem would be to change the loop to start at the last letter in the string and use the push method instead of unshift. Since push attaches each new element onto the end of the array instead of the front, it doesn’t need to loop through and update the index of every element. This is efficient, but I think there’s an even more efficient way to solve this problem.

This solution isn’t going to be too complicated, it’s based off of chaining methods to transform the strings. First, the string variable will be the same as the previous solution listed above. Then, to get the reversed version of that string, all that needs to be done is to use the split method on that string to divide each letter into a separate element in an array, reverse that array with the reverse method, and rejoin the array into a string by using join with an empty string passed in as an argument. Finally, for the return statement. The check should just be if the string variable is deeply equal to the reversed variable. This will give back a passing solution!

A more efficient solution
Final solution runtime chart

Those numbers are much better! By thinking creatively and optimizing your functions, you’re able to make your code run significantly faster and more efficiently. By removing some loops and cleaning up some aspects of this palindrome function, I was able to make the function run over six times faster. This challenge was a great lesson in efficiency and optimization.