What is the best approach for 'Find the Closest Palindrome' problem?

Use string-based mirroring of the first half with small adjustments, plus boundary checks, to avoid brute force over huge numbers.

Why can't I just iterate over all numbers to find the closest palindrome?

Iterating over all numbers is too slow for n up to 10^18; string manipulation creates only relevant candidates efficiently.

How are ties handled when two palindromes are equally close?

Always choose the smaller numeric palindrome when absolute differences are equal.

Are single-digit numbers treated differently?

Yes, for n = "1" to "9", the closest palindrome can be 0 or n-1, handled explicitly to respect tie-breaking rules.

What edge cases should I watch for in this Math plus String pattern problem?

Watch for numeric boundaries like 10^k + 1, 10^(k-1) - 1, and cases where adjusting the mirrored prefix changes the closest palindrome.

#564

Hard

auto_awesome数学·string

LeetCode 题解工作台

寻找最近的回文数

给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。 “最近的”定义为两个整数差的绝对值最小。示例 1: 输入: n = "123" 输出: "121" 示例 2: 输入: n = "1" 输出: "0" 解释: 0 和 2是最近的回文，但我们返…

数学字符串

题目描述

给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。

“最近的”定义为两个整数差的绝对值最小。

示例 1:

输入: n = "123"
输出: "121"

示例 2:

输入: n = "1"
输出: "0"
解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。

提示:

1 <= n.length <= 18
n 只由数字组成
n 不含前导 0
n 代表在 [1, 10¹⁸ - 1] 范围内的整数

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        x = int(n)
        l = len(n)
        res = {10 ** (l - 1) - 1, 10**l + 1}
        left = int(n[: (l + 1) >> 1])
        for i in range(left - 1, left + 2):
            j = i if l % 2 == 0 else i // 10
            while j:
                i = i * 10 + j % 10
                j //= 10
            res.add(i)
        res.discard(x)

        ans = -1
        for t in res:
            if (
                ans == -1
                or abs(t - x) < abs(ans - x)
                or (abs(t - x) == abs(ans - x) and t < ans)
            ):
                ans = t
        return str(ans)

speed

复杂度分析

指标	值
时间	complexity is O(n \cdot log(m)) where n is the length of the string and m is the numeric value used for adjustments. Space complexity is O(n) to store candidate strings and mirrored computations.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Check if a brute force approach will scale for n up to 10^18.
question_mark
Consider how string manipulation can generate palindromes instead of numeric iteration.
question_mark
Ask about tie-breaking rules when multiple palindromes are equally close.

warning

常见陷阱

外企场景

error
Failing to exclude the input number itself when generating closest palindromes.
error
Overlooking edge palindromes like 10^k + 1 or 10^(k-1) - 1 which are crucial for very small or large n.
error
Incorrect tie-breaking logic that returns the larger palindrome instead of the smaller one.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the closest palindrome larger than the given number.
arrow_right_alt
Find the closest palindrome smaller than the given number.
arrow_right_alt
Count the number of palindromes within a given numeric range.

help

常见问题

外企场景

继续练习

#556 下一个更大元素 III #539 最小时间差 #537 复数乘法