LeetCode: Find the Closest Palindrome

Posted on February 28, 2018March 30, 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
##   Identity all the candiates
##
##   Length smaller by one: 999
##   The same length: ..Y.., ..(Y-1).., ..(Y+1)..
##   Length greater by one: 1001
##
## Complexity: Time ?, Space ?
class Solution:
    def nearestPalindromic(self, n: str) -> str:
        cnt = len(n)
        # 10..01, 9..9
        candidates = [str(10**cnt+1), str(10**(cnt-1)-1)]
        left = int(n[:int((cnt+1)/2)])
        for v in [left, left+1, left-1]:
            # even
            if cnt%2 == 0:
                candidates.append(str(v)+str(v)[::-1])
            else:
                candidates.append(str(v)+str(v)[:-1][::-1])
        def delta(s):
            return abs(int(s)-int(n))

        res = None
        for c in candidates:
            # skip itself
            if c == n: continue
            if not res: res = c
            # find a better candidate
            if delta(c) < delta(res):
                res = c
            elif delta(c) == delta(res) and int(c)<int(res):
                # find a tie
                res = c
        return res

Post Views: 8