Find the Closest Palindrome
Intuition
Solution
class Solution:
def nearestPalindromic(self, n: str) -> str:
l = len(n)
candidates = []
if len(n) % 2 == 1:
# 12345 -> 12321, 23432 -> 23532 and 23332
prefix = n[:l // 2 + 1]
for tmp in [str(int(prefix) + 1), str(int(prefix) - 1), prefix]:
candidates.append(tmp[:-1] + tmp[::-1])
else:
prefix = n[:l // 2]
for tmp in [str(int(prefix) + 1), str(int(prefix) - 1), prefix]:
candidates.append(tmp + tmp[::-1])
# 100...01, 99...99
candidates.append(str(10 ** l - 1))
candidates.append(str(10 ** (l - 1) - 1))
candidates.append(str(10 ** l + 1))
candidates.append(str(10 ** (l - 1) + 1))
candidates.sort(key=int)
target, diff = None, None
for n2 in candidates:
if n != n2 and (diff is None or abs(int(n) - int(n2)) < diff):
diff = abs(int(n) - int(n2))
target = n2
return target