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