blob: 12f44fe8b061bad98e4792480b0e6c520a752278 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
# 564. Find the Closest Palindrome
"""
given a string 'n' representing an integer, return the closest integer (not
including itself), which is a palindrome. if there is a tie, return the
smaller one. the closest is defined as the absolute difference minimised
between two integers.
"""
class Solution(object):
def nearestPalindromic(self, n):
"""
:type n: str
:rtype: str
"""
if int(n) <= 10 or (int(n) % 10 == 0 and int(n[1:]) == 0):
return str(int(n) - 1)
elif int(n) == 11 or (int(n) % 10 == 1 and n[0] == "1" and int(n[1:-1]) == 0):
return str(int(n) - 2)
elif n[0] == "9" and n[0] * len(n) == n:
return str(int(n) + 2)
else:
def get_panindrome(base, is_even_length=True):
if is_even_length:
return base + "".join(reversed(base))
else:
return base[:-1] + base[-1] + "".join(reversed(base[:-1]))
even_size = len(n) % 2 == 0
palindrome_base = (
int(n[0 : len(n) // 2]) if even_size else int(n[0 : len(n) // 2 + 1])
)
is_n_palindrome = get_panindrome(str(palindrome_base), even_size) == n
base_candidates = (
[palindrome_base - 1, palindrome_base + 1]
if is_n_palindrome
else [palindrome_base - 1, palindrome_base, palindrome_base + 1]
)
diff = float("inf")
for base_candidate in base_candidates:
candidate = int(get_panindrome(str(base_candidate), even_size))
if abs(candidate - int(n)) < diff:
diff = abs(candidate - int(n))
min_base_candidate = str(base_candidate)
return get_panindrome(min_base_candidate, even_size)
if __name__ == "__main__":
obj = Solution()
print(obj.nearestPalindromic("123"))
print(obj.nearestPalindromic("1"))
|