Solution by awice


  • 0

    Approach #1: Convert to String [Accepted]

    Intuition

    It is easy to check whether a string is a palindrome, so let's first convert the integer to a string.

    Algorithm
    Recall that a palindrome is a string that reads the same forwards and backwards. We can check if a string $$S$$ is a palindrome in two ways. One way is that $$S$$ must be equal to it's reverse. Another way is to check that every digit $$i$$ places from the beginning, equals the digit $$i$$ places from the end. With 0-based indexing, this means that $$S[i] == S[len(S) - 1 - i]$$.

    Python

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

    Alternate Implementation

        def isPalindrome(self, x):
            s = str(x)
            return s == s[::-1]
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the length of the number. We need to convert the integer to string, and read every digit.

    • Space Complexity: $$O(N)$$ additional space is used to store the string.


    Approach #2: Calculate the Reverse of the Integer [Accepted]

    Intuition

    If somehow we could reverse an integer, we would only need to check whether $$x$$ equals $$reverse(x)$$.

    Algorithm

    We can build the reversed integer of $$x$$ by repeatedly removing the last digit $$x% 10$$, and adding that to the end of our current answer by $$ans = 10 * ans + (x % 10)$$.

    Negative integers are never palindromes, so we should also take care to handle that case appropriately.

    Python

    class Solution(object):
        def isPalindrome(self, x):
            def reverse(x):
                ans = 0
                while x:
                    ans = 10 * ans + x % 10
                    x /= 10
                return ans
                
            return x >= 0 and x == reverse(x)
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the length of the number. We take $$N$$ steps in our while loop to compute the reversed integer. Alternatively, this would be $$O(\log_{10}{x})$$ where $$x$$ is the given number.

    • Space Complexity: If the integer is guaranteed to fit in say, 32 or 64 bits, then there is $$O(1)$$ additional space used for the reversed integer. Otherwise, if the integer is arbitrarily big, then $$O(N)$$ additional space is used to store the reversed integer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.