Нахождение следующего большого палиндрома числа

Question

Я пытался решить проблему для следующего по величине палиндрома на SPOJ, но это бросает мне лимит времени Превышенная ошибка. Это мой подход к проблеме в питоне,

t = int(raw_input().strip()) 

for i in range(t): 
    a = raw_input() 
    a = str(int(a) + 1) 
    palin = "" 

    if (len(a) % 2 == 0): 

     reverseoffirst = [] 
     mainStr = a 

     firsthalf = mainStr[0:len(a)/2] 
     secondhalf = firsthalf[::-1] 

     palin = "".join(firsthalf) + "".join(secondhalf) 

     if (int(palin) < int(a)): 
      firsthalf = str(int(firsthalf) + 1) 
      secondhalf = firsthalf[::-1] 
      palin = "".join(firsthalf) + "".join(secondhalf) 


    else: 
     median = len(a)/2 
     mainStr = a 

     if(median == 0): 
      palin = "11" 

     else: 
      firsthalf = mainStr[0:median] 
      secondhalf = firsthalf[::-1] 

      palin = "".join(firsthalf) + mainStr[median] + "".join(secondhalf) 

      if (int(palin) < int(a)): 
       lastvalue = int(mainStr[median]) + 1 

       if (lastvalue == 10): 
        firsthalf = str(int(firsthalf) + 1) 
        secondhalf = firsthalf[::-1] 
        palin = firsthalf + "0" + secondhalf 

       else: 
        palin = firsthalf + str(lastvalue) + secondhalf 
    print palin 

Я знаю, что мой вопрос может получить downvoted за то, что дубликат несколько вопросов, как это, но мой подход не копируется из любого места. Вот почему я хотел знать, что не так с моим кодом.

Пожалуйста, если вы можете указать любой способ, которым этот код может получить лучше или какой-либо тест, который он не удовлетворяет, или какой-либо другой подход, который был бы очень полезен для меня. Спасибо!!

Answer 1

Я взял ваш код и немного изменил его, чтобы ваша логика была такой же.

Попробуйте отладить его, чтобы вы поняли, как он работает лучше.

Обратите внимание, что он будет работать только для цифр, а не для букв.

В принципе, по вашей логике, я проверил, что присоединиться к первой половине со второй половины является следующий палиндром

Успехов

a = str(int(input())) # the initial number to check 
is_palin = False 
while True: 
    a = str(int(a) + 1) 
    if is_palin: 
     print palin 
     break 
    palin = "" 

    if (len(a) % 2 == 0): 

     reverseoffirst = [] 
     mainStr = a 

     firsthalf = mainStr[0:len(a)/2] 
     secondhalf = firsthalf[::-1] 

     palin = "".join(firsthalf) + "".join(secondhalf) 

     if (int(palin) == int(a)): 
      is_palin = True 
      print palin 


    else: 
     median = (len(a)/2) 
     mainStr = a 
     firsthalf = mainStr[0:median] 
     secondhalf = firsthalf[::-1] 
     palin = "".join(firsthalf) + mainStr[median] + "".join(secondhalf) 
     if (int(palin) == int(a)): 
      is_palin = True 
      print palin 

Answer 2

Возможно, не самый эффективный метод никогда:

def IsPalindrome(n): 
     s = str(n) 
     l = len(s) 
     return s[:l/2] == s[:(l+1)/2-1:-1] 

def NextPalindrome(n): 
     while not IsPalindrome(n): 
       n += 1 
     return n 

Но NextPalindrome(65973) возвращает 66066 мгновенно.