# 564. Find the Closest Palindrome

• Time:
• Space:
  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 class Solution { public: string nearestPalindromic(string n) { const auto& [prevPalindrome, nextPalindrome] = getPalindromes(n); return abs(prevPalindrome - stol(n)) <= abs(nextPalindrome - stol(n)) ? to_string(prevPalindrome) : to_string(nextPalindrome); } private: pair getPalindromes(const string& s) { const long num = stol(s); const int n = s.length(); pair palindromes; const string& half = s.substr(0, (n + 1) / 2); const string& reversedHalf = reversed(half.substr(0, n / 2)); const long candidate = stol(half + reversedHalf); if (candidate < num) palindromes.first = candidate; else { const string& prevHalf = to_string(stol(half) - 1); const string& reversedPrevHalf = reversed(prevHalf.substr(0, n / 2)); if (n % 2 == 0 && stol(prevHalf) == 0) palindromes.first = 9; else if (n % 2 == 0 && (stol(prevHalf) + 1) % 10 == 0) palindromes.first = stol(prevHalf + '9' + reversedPrevHalf); else palindromes.first = stol(prevHalf + reversedPrevHalf); } if (candidate > num) palindromes.second = candidate; else { const string& nextHalf = to_string(stol(half) + 1); const string& reversedNextHalf = reversed(nextHalf.substr(0, n / 2)); palindromes.second = stol(nextHalf + reversedNextHalf); } return palindromes; } string reversed(const string& s) { return {rbegin(s), rend(s)}; } }; 
  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 class Solution { public String nearestPalindromic(String n) { final long[] palindromes = getPalindromes(n); return Math.abs(palindromes[0] - Long.parseLong(n)) <= Math.abs(palindromes[1] - Long.parseLong(n)) ? String.valueOf(palindromes[0]) : String.valueOf(palindromes[1]); } private long[] getPalindromes(final String s) { final long num = Long.parseLong(s); final int n = s.length(); long[] palindromes = new long[2]; final String half = s.substring(0, (n + 1) / 2); final String reversedHalf = new StringBuilder(half.substring(0, n / 2)).reverse().toString(); final long candidate = Long.parseLong(half + reversedHalf); if (candidate < num) palindromes[0] = candidate; else { final String prevHalf = String.valueOf(Long.parseLong(half) - 1); final String reversedPrevHalf = new StringBuilder(prevHalf.substring(0, Math.min(prevHalf.length(), n / 2))) .reverse() .toString(); if (n % 2 == 0 && Long.parseLong(prevHalf) == 0) palindromes[0] = 9; else if (n % 2 == 0 && (Long.parseLong(prevHalf) + 1) % 10 == 0) palindromes[0] = Long.parseLong(prevHalf + '9' + reversedPrevHalf); else palindromes[0] = Long.parseLong(prevHalf + reversedPrevHalf); } if (candidate > num) palindromes[1] = candidate; else { final String nextHalf = String.valueOf(Long.parseLong(half) + 1); final String reversedNextHalf = new StringBuilder(nextHalf.substring(0, n / 2)).reverse().toString(); palindromes[1] = Long.parseLong(nextHalf + reversedNextHalf); } return palindromes; } } 
  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 class Solution: def nearestPalindromic(self, n: str) -> str: def getPalindromes(s: str) -> tuple: num = int(s) k = len(s) palindromes = [] half = s[0:(k + 1) // 2] reversedHalf = half[:k // 2][::-1] candidate = int(half + reversedHalf) if candidate < num: palindromes.append(candidate) else: prevHalf = str(int(half) - 1) reversedPrevHalf = prevHalf[:k // 2][::-1] if k % 2 == 0 and int(prevHalf) == 0: palindromes.append(9) elif k % 2 == 0 and (int(prevHalf) + 1) % 10 == 0: palindromes.append(int(prevHalf + '9' + reversedPrevHalf)) else: palindromes.append(int(prevHalf + reversedPrevHalf)) if candidate > num: palindromes.append(candidate) else: nextHalf = str(int(half) + 1) reversedNextHalf = nextHalf[:k // 2][::-1] palindromes.append(int(nextHalf + reversedNextHalf)) return palindromes prevPalindrome, nextPalindrome = getPalindromes(n) return str(prevPalindrome) if abs(prevPalindrome - int(n)) <= abs(nextPalindrome - int(n)) else str(nextPalindrome)