Checking for :
Palindromes | semordnilaP
Going through algorithms and practice questions, we all have come across a palindrome or two. If you haven’t, you will run in to one soon. So what is a palindrome you ask?
A palindrome is a word, phrase, number or a sequence of characters that reads the same backward or forward. These are examples of palindromes:
7189999817, “Dammit I’m mad”, “@a123bccb321a@”
Now that we know what a palindrome is, lets see if we came check if an integer input is a palindrome in one of the most common leet code questions: palindrome number.
In the problem, we are given an integer. We will either return true if it is a palindrome, or false if not. Since we are working with numbers, there is an immediate edge case where if the integer is a negative, then it is not a palindrome base on the extra minus sign in front. Another edge case we can think of is if the integer is 10 or a multiple of 10, we know it is not a palindrome.
Based on my initial thought, I am going to use the two pointer method. If you need a refresher on the two pointer method, you can check my previous blog on the two pointer method. In order for the two pointers to work, we first need to convert the integer to an array of strings. Then we set a left and a right pointer at the two ends of the array. If the two ends are equal, then we will move the left pointer to the right and simultaneously the right pointer to the left. We will continue this while loop until we get a true or false.
In this approach, our time complexity is O(len n) depending on the length of the array, and has a best case scenario of O(n). Since our output is either true or false, our space complexity is O(1).
Another way we could solve this problem is again change the integer into a string. Then we reverse the array and check if the reversal is equal to the initial input.
Once again since we are converting this in to an array again, our time complexity would range from O(len n) (worst case) to O(n) (best case) and has a space complexity of O(1).
One more way of checking for an integer palindrome involves a little bit of math. We would setup a copy (label current) of the initial input and an inverted version of the input. What we are doing here is taking the initial input and fill it in backwards in to inverted.
First, lets fill out our inverted input. We take our inverted value and multiply it by 10, and add the modulo 10 remainder of the current copy (121). This would update our inverted value to 1. Then we take our current copy and divide by 10 and round it down to the nearest number. This would update our current value to 12. We would run this while loop as long as we have a value greater than zero for our current copy or as long as our input(x) is greater than our inverted value. Lastly we compare and see if our inverted value is equal to our initial input.
Above is a step by step change of the value of our current copy and our inverted integer. The time complexity of this method will be O(n) and the space will be O(1). If you are interested in more ways of solving this problem you can also search for the recursion version.
