Leetcode: Find the Closest Palindrome

Posted on February 28, 2018January 5, 2020 by braindenny

Find the Closest Palindrome

Similar Problems:

Given an integer n, find the closest integer (not including itself), which is a palindrome.

The ‘closest’ is defined as absolute difference minimized between two integers.

Example 1:
Input: "123"
Output: "121"

Note:

The input n is a positive integer represented by string, whose length will not exceed 18.
If there is a tie, return the smaller one as answer.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/find-the-closest-palindrome
## Basic Ideas: Greedy. Try our best to keep the high digits
##
## Complexity: Time O(n), Space O(1)
class Solution(object):
    def nearestPalindromic(self, n):
        """
        :type n: str
        :rtype: str
        """
        length = len(n)
        if length == 1: return str(int(n)-1)

        k = int(length/2)
        first_half = n[0:k]
        # why this?
        # 10 -> 9
        if length%2 == 1:
            n2="%s%s%s" % (first_half, n[k], first_half[::-1])
        else:
            n2="%s%s" % (first_half, first_half[::-1])

        if n!= n2: return n2

        if length%2==1:
            # 20202 -> 20102
            if n[k+1] == '0': ch = '1'
            else: ch = str(int(n[k])-1)
            return "%s%s%s" % (first_half, ch, first_half[::-1])
        else:
            if n[k] == '0': ch = '1'
            else: ch = str(int(n[k-1])-1)
            res = "%s%s%s%s" % (first_half[:-1], ch, ch, first_half[:-1][::-1])
            ## 11 -> 00 -> 0
            return str(int(res))

Post Views: 8