Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Find the Closest Palindrome

Posted on February 28, 2018July 26, 2020 by braindenny

Find the Closest Palindrome



Similar Problems:

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #palindrome, #string, #greedy

Given an integer n, find the closest integer (not including itself), which is a palindrome.

The ‘closest’ is defined as absolute difference minimized between two integers.

Example 1:
Input: "123"
Output: "121"

Note:

  1. The input n is a positive integer represented by string, whose length will not exceed 18.
  2. If there is a tie, return the smaller one as answer.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/find-the-closest-palindrome
## Basic Ideas
##   Identity all the candiates
##
##   Length smaller by one: 999
##   The same length: ..Y.., ..(Y-1).., ..(Y+1)..
##   Length greater by one: 1001
##
## Complexity: Time ?, Space ?
class Solution:
    def nearestPalindromic(self, n: str) -> str:
        cnt = len(n)
        # 10..01, 9..9
        candidates = [str(10**cnt+1), str(10**(cnt-1)-1)]
        left = int(n[:int((cnt+1)/2)])
        for v in [left, left+1, left-1]:
            # even
            if cnt%2 == 0:
                candidates.append(str(v)+str(v)[::-1])
            else:
                candidates.append(str(v)+str(v)[:-1][::-1])
        def delta(s):
            return abs(int(s)-int(n))

        res = None
        for c in candidates:
            # skip itself
            if c == n: continue
            if not res: res = c
            # find a better candidate
            if delta(c) < delta(res):
                res = c
            elif delta(c) == delta(res) and int(c)<int(res):
                # find a tie
                res = c
        return res
linkedin
github
slack

Post Views: 8
Posted in HardTagged #greedy, #palindrome, #string, redo

Post navigation

LeetCode: Longest Line of Consecutive One in Matrix
LeetCode: Relative Ranks

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.