menu

[LeetCode] 009. Palindrome Number

Problem (Medium)

009. Palindrome Number

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

Example 1:

  • 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.

Example 3:

  • Input: 10
  • Output: false
  • Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Could you solve it without converting the integer to a string?

Approach 1: Convert Number to String

Idea

Pretty straightforward, just convert the input number to string, then verify s[i] ?= s[-i-i], where i < len(s)//2.

Solution

class Solution1:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        if len(s) == 1:
            return True
        for i in range(len(s)//2):
            if s[i] != s[-1-i]:
                return False
        return True

Complexity

  • Time: $O(n)$
  • Space: $O(n)$

Approach 2: Numeric Check

Idea

The reversed number should be equal to the original number when it’s palindrome.

Solution

class Solution2:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        original = x
        reverse = 0
        while x:
           reverse *= 10 
           reverse +=  x % 10
           x //= 10
        return reverse == original

Complexity

  • Time: $O(n)$
  • Space: $O(n)$

Approach 2 Update: Check Only Half of the digits

Idea

when reverse > x, the checking loop reaches middle.

Solution

class Solution2_update:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False 
        if x and x % 10 == 0:
            return False
    
        reverse = 0 
        while x > reverse: 
           reverse *= 10  
           reverse +=  x % 10
           x //= 10
        print(reverse, x)
        return reverse == x or reverse // 10 == x

Complexity

  • Time: $O(n)$
  • Space: $O(n)$



KF

Comments