Palindrome Checker
November 26th, 2020
I love the Palindrome Checker problem.
What's a palindrome?!
a word, verse, or sentence (such as "Able was I ere I saw Elba") or a number (such as 1881) that reads the same backward or forward
This challenge asks you to write a function to check if a string is a palindrome.
It may seem complicated, but there is a really easy solution.
First, let's look at a less optimal solution.
Typical strategy.
Why is this not optimal?
This strategy is always O(n).
Hey, wait, what is O(n)?!
If you've never heard the term, check out this great article from Beau Carnes:
Big O Notation — Simply explained with illustrations and video
Each time the above function runs, the entire string has to be reversed, which means the whole things is iterated over every time. The function looks at each item, each time. That's fine if you have a short string, but what if your input is book length? And the first two items don't even match? I think we can do better!
You don't need to worry about anything fancy. All you really need to do, is compare the first item to the last item. If they match, move on to the next two. Compare, move on. And it's more efficient than the typical strategy above!
Here's how:
1. Start at the beginning with one pointer.
2. Start at the end with another.
3. Loop.
Do the first and last items match?
No? Return false! You're done. No need to keep looking.
This makes the code much more efficient. You don't have to go through every item of the string. So, best case scenario you can beat O(n).
However, if it's the string really is a palindrome, the function will have to iterate over each element in the string. That means the longer the string, the longer the function will take to run. So, the time complexity increases as the length of the string increases. So, worst case scenario, we're still at O(n).
My Solution
Edge Cases
If your strings are not all the same case, you could add code to make them all lowercase (or uppercase)
let sameCaseString = string.toLowerCase()
If you may have white spaces in your input, get rid of them with a simple regex:
let noWhiteSpaceString = .replace(/[\W_]/g, "")
You could also just chain these methods together:
let improvedString = string.toLowerCase().replace(/[\W_]/g, "")
But, the first solution is shorter!
Shorter is not always better. Yes, the Typical Solution is less characters in the text editor, but that's no way to evaluate code.
Better questions for evaluating code:
Can I understand it quickly?
Is it optimized for space-time complexity?
Questions?
Know a better way?
Get in touch!
Happy coding! Rebecca