Coder's Cat

LeetCode: Palindrome Number

2019-10-21

LeetCode: Palindrome number, explanation and solution with C++/Java/Python

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

LeetCode Problem

https://leetcode.com/problems/palindrome-number/

Example:

Input: 121
Output: true
Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Explanation

This problem is easy, according to problem description:

If $input < 0$, it must not be palindrome number.

If $input < 10$, it’s length is 1, and it must be a palindrome number.

Otherwise, we reverse the number by digits, and check whether equal with origin number.

Note the edge case of integer overflow when reversing a number:

Line 7: Char 23: runtime error: signed integer overflow: 746384741 * 10 cannot be represented in type 'int' (solution.cpp)

We need to avoid this in the loop.

An alternative solution is converting an integer into string, then check str with reverse(str).

C++

class Solution {
public:
int reverse(int x) {
if(x == 0) return 0;
int res = 0;
for(; x; x /= 10) {
int n = (x % 10);
if (res >= INT_MAX/10 - n )
return -1;
res = res * 10 + n;
}
return res;
}
bool isPalindrome(int x) {
if(x<0) return false;
return x == reverse(x);
}
};

Java

class Solution {
public boolean isPalindrome(int x) {
if (x < 0) {
return false;
}
int n = x;
int rev = 0;
while (n > 0) {
int t = n % 10;
if(rev >= Integer.MAX_VALUE/10 + n%10)
return false;
rev = 10 * rev + t;
n /= 10;
}
return rev == x;
}
}

Python

In Python, str(x) will convert x into string, with extended slice index, s[start:stop:step] can be used for fetch substring of a string.

And s[::-1] reverse string using slicing, -1 denotes starting from end and stop at the start, hence reversing string.

class Solution:
def isPalindrome(self, x: int) -> bool:
return str(x) == str(x)[::-1]

Preparing for an interview? Check out this!