LeetCode: Find the Closest Palindrome Posted on February 28, 2018July 26, 2020 by braindenny Find the Closest Palindrome Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #palindrome, #string, #greedy 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