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”.
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.
We have a successful function! Let’s check the 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!
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.