Palindrome Number
franklinqin0 Math
# Solution
Let be x
. So there are digits in total.
# Convert to String & Compare Chars
Complexity
time: ( per digit)
space: (int x
is converted to string s
)
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x > 10 and x % 10 == 0):
return False
# convert int to str
s = str(x)
l = 0
r = len(s) - 1
while l < r:
# compare left and right digits
if s[l] != s[r]:
return False
else:
l += 1
r -= 1
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 1-line Solution
Rather than doing the char comparison in a while loop, use ::-1
in Python to do string reversion and compare w/ ==
operator.
Complexity
time:
space:
def isPalindrome(self, x: int) -> bool:
return str(x) == str(x)[::-1]
1
2
2
# Follow Up
Could you solve it without converting the integer to a string?
Let's first do vanilla int comparison.
# Revert an Integer & Compare Ints
ri
means reversed int.
If x
is , at the end of the while loop we get x
= 12, ri
= 123. ri//10
= 12, equal to x
, so returns True
.
If x
is , at the end of the while loop we get x
= 12, ri
= 12, equal to x
, so returns True
.
Complexity
time: ( per digit)
space: (no string initialized)
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x != 0 and x % 10 == 0): return False
ri = 0
while ri < x:
ri = ri*10 + x%10
x //= 10
# since the middle digit doesn't matter in an odd palidrome(it will always equal to itself)
# we can simply get rid of it by ri//10
return ri == x or ri // 10 == x
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9