Repeat Code With LeetCode — Valid Palindrome
Thanks to FryingPan, this question is now a meme
Thanks to a viral YouTube video, this LeetCode interview question is now a meme. They also try to solve it incorrectly, which I like to think is part of the lore: The interviewer intentionally misguides the candidate, then proceeds to completely berate him for failing to follow his bad advice.
Can you solve this question using a stack? Sure, I guess so. Is that the cleanest, most efficient, or easiest solution? No, and a stack implementation is not even listed on LeetCode’s own solution page. They suggest two approaches.
The first approach is one you probably thought of already. Just reverse the string. Reversing the string is its own interview question because you can do it in-place using the Two Pointer Technique, but there is no benefit to doing that here. If you were to reverse a string in-place for this problem, you would still have to hold a copy of the original string and that would defeat the purpose because of space complexity.
That is good news for us. Here is the easy way to do the problem.
Make a new string. Build it in reverse order. Check to see if the original string is equal to the reverse string.
Side Tangent: The Two Pointer Technique
You can read about the Two Pointer Technique here.
I have never heard of the Two Pointer Technique until I got LeetCode. As far as I know, though anyone is welcome to correct me, it is not really significant for anything except coding interviews. It also has a name that somewhat suggests that it relates to C/C++ pointers, which is half-right. You use the Two Pointer Technique to keep track of two indices. It is also explained very well here.
The Problem
Problem: Valid Palindrome
Difficulty: Easy
Skills Required: Two Pointer Technique (depending on implementation)
Fun Facts: Featured in a FryingPan YouTube video; part of Blind75
Description: A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
So…this problem took me some serious debugging, though I debated the usefulness of sharing my whole “journey” with you. Suffice to say, lines 17–20 were the big “breakthrough” for me. Before that, start was going past end.
Fundamentally, the problem solution is straightforward. What you are doing is similar to what you do in the reverse string problem, if you solved that using the Two Pointer Technique. I am sharing that here as well.
I am not sure if “reverse a string” deserves its own post, but here is code you can use to solve it. Instead of constructing an entirely new string, which would be far too simple and straightforward to satisfy your high-maintenance interviewer, you can use one pointer for the start of your string and one pointer for the end of your string. Then you go from two sides and swap.
That brings us back to isPalindrome. Do you use the same algorithm? No, but you do something similar. You use one pointer for the start of your string, one pointer for the end, and you continually check to see that both pointers are at the same letter.
My code avoids the confusing for loop in the LeetCode premium solution (for (int i = 0, j = s.size() — 1; i < j; i++, j — ) {) , but it also does some things worse. For example, I did not know about the C++ function isalnum, so I went for the more confusing method of individually verifying that we skipped characters that were spaces or not alphanumeric. Before getting to this, I had never put a while loop inside a for loop before.
- Use the Two Pointer Technique, one pointer for the start of your string and one for your end
- Verify that the start pointer always points to the same letter or digit as the end pointer. Keep moving both pointers until you find a violation. If you fail to find any violation, then return true
- The while loops could require a mental leap, but they are there to ensure you skip all “unimportant characters”
Closing Thoughts
I was not sure what to put here, so here is a YouTube video of a golden retriever ringing a doorbell.
