Найти самый большой палиндром в любой заданной строке, используя python (примечание большой O)

Question

Мне было интересно, какой вид O это код, может ли кто-нибудь помочь мне разобраться? Я написал это, но когда меня допрашивали, о какой O-нотации, и единственное, что я могу сказать, было линейным, но у меня такое ощущение, что рекурсия + итерация должна быть экспоненциальной?

listPlindromes = [] 

def palindrome(givenString, n): 
    if n == 1: 
     #print givenString 
     return None 
    else: 
     #print givenString[:n] 
     #print ('forward: '+givenString[:n] +' backwards: '+givenString[:n][::-1]) 

     #Get difference between lengths 
     lenDifference = len(givenString) - len(givenString[:n]) 

     #If there is a difference means there at least one more word/palindrome could exist 
     #therefore it need to be tested 
     if lenDifference > 0: 
      for xTest in range(0,lenDifference-1) : 
       newWord=givenString[xTest:n+xTest] 
       if newWord == newWord[::-1]: 
        if len(newWord) > 0: 
         listPlindromes.append(newWord) 
         #print newWord 
     else: 
      if givenString[:n] == givenString[:n][::-1]: 
        listPlindromes.append(givenString[:n]) 
      #print('palindrome: '+givenString) 

     return palindrome(givenString,n-1) 

givenString='osooso' 

palindrome(givenString, len(givenString)) 
print(listPlindromes) 

Answer 1

Код, который у вас там есть, проходит в линейном времени; то есть его основным узким местом является то, насколько велика ваша строка.

Тем не менее, есть некоторые вещи, которые могут быть улучшены:

• Вам нужно только передать строку
• Строка длины 1 палиндром
• Там много ненужных/ненужные проверки длины; просто нарезка строки в половине будет достаточно, чтобы начать свои чеки

В итерационном + рекурсивного подхода, это действительно зависит от того, как он является автором, но у меня есть рекурсивный подход в виде, который может быть O (п) также.

• Начать с цепочки.
• Если оба конца совпадают:
  • Если длина одной стороны * строки больше 1, взять кусочек его с этой позиции до 1 меньше, чем последний символ.
  • Вызывать функцию.
• Если оба конца совпадают, а длина одной стороны * строки меньше или равна 1, мы закончили - вернем true.
• В противном случае:
  • Возврат false, так как мы обнаружили несоответствие.

^{*: Независимо от того, является ли строка четной или нечетной, разрезая его пополам даст вам четное количество символов с обеих сторон.}

Answer 2

Простое решение:

def palchecker(aString): 
    aString = aString.lower() 
    reverse = aString[::-1] 

    if aString == reverse: 
     return True 

    return(False) 

print(palchecker("lsdkjfskf")) 
print(palchecker("aIbohPhoBiA"))