Je voudrais trouver le palindrome le plus long d'une corde donnée.
puis imprimez-le
geeksskeeg
Ma sortie actuelle: sskeegfor
attendue devrait être:
lines = "forgeeksskeegfor" length = len(lines) a = [lines[i:j+1] for i in range(length) for j in range(i, length)] total = [] for string in a: list(string).reverse() reverse_String = "".join(string) if reverse_String == string.lower(): total.append(reverse_String) print(max(total))
c'est la longueur 10 et la plus longue
6 Réponses :
au lieu de rechercher le maximum d'une liste de «chaînes», vous devriez rechercher la longueur maximum. en fonction de votre approche.
for string in a: # the below line will not change anything # you are just converting a string to list on the fly # reversing it ,but not storing it somewhere list(string).reverse() # string is still string of a , and reverse_String and string # both will be same. reverse_String = "".join(string) # not sure why are you converting to lower here if reverse_String == string.lower(): total.append(reverse_String)Hope it helps
Il y a un défaut dans votre test de palindrome.
lines = "forgeeksskeegfor" length = len(lines) a = [lines[i:j+1] for i in range(length) for j in range(i, length)] total = [] for string in a: if string == string[::-1]: total.append(string) max_len = max( [ len(x) for x in total ] ) # result list will contain the longest pallindroms result_list = [ x for x in total if len(x) == max_len ]
J'espère que cela aide.
Mais le résultat que j'ai imprimé est différent de ce que j'attends
mis à jour ma réponse, en fait quand vous faites list (string) .reverse () cela ne change rien.
Cela peut être résolu avec une programmation dynamique
Le code suivant a un pire temps d'exécution de 2 ^ n lorsqu'il n'y a pas de palindrome dans la chaîne, il essaiera donc toutes les solutions possibles.
Mais ses performances augmentent à mesure qu'il trouve un palindrome.
def find_pal(string, start, end): # base case if end - start <= 1: return (start, end) # if a palindrome shows: elif string[start] == string[end]: # check if its substring is a palindrome also next_pal = find_pal(string, start + 1, end - 1) if next_pal == (start + 1, end - 1): # if it is, then return the longer return (start, end) else: # if it is not, still return any smaller palindrome in string return next_pal else: # if this string is not a palindrome, check for a smaller in a substring next_pal1 = find_pal(string, start + 0, end - 1) next_pal2 = find_pal(string, start + 1, end - 0) if next_pal1[1] - next_pal1[0] > next_pal2[1] - next_pal2[0]: return next_pal1 else: return next_pal2 def find_greatest_pal(string): pal_pair = find_pal(string, 0, len(string)-1) return string[pal_pair[0]:pal_pair[1]+1] print(find_greatest_pal("forgeeksskeegfor"))
L'idée est d'itérer dans la chaîne et de générer tous les palindromes en partant du centre et en se déplaçant vers les deux côtés. Si nous trouvons un palindrome supérieur à notre longueur actuelle, nous le remplaçons par le nouveau.
print(longestPalindrome('forgeeksskeegfor')) geeksskeeg
Usage:
def longestPalindrome(s): ans = "" for i in range(len(s)): for k in range(2): temp = helper(s, i, i + k) if len(temp) > len(ans): ans = temp return ans def helper(s, l, r): while l >= 0 and r < len(s) and s[r] == s[l]: l -= 1 r += 1 return s[l+1:r]
Il existe deux scénarios de palindrome: les palindromes pairs (par exemple midi) et les palindromes impairs (par exemple radar). Il n'y a que deux palindromes possibles (les plus longs) pour chaque position dans la corde. Ainsi, pour chaque position, il vous suffit de trouver les palindromes pairs et impairs les plus longs centrés à cette position en comparant les caractères en avant et en arrière.
from itertools import zip_longest def binRange(lo,hi=None): if hi is None: lo,hi = 0,lo if hi <= lo: return mid = (lo+hi-1)//2 yield mid for a,b in zip_longest(binRange(lo,mid),binRange(mid+1,hi),fillvalue=None): if a is not None: yield a if b is not None: yield b
Remarque: cela pourrait être encore optimisé mais répondra en temps O (n) la plupart du temps ou jusqu'à O (n ^ 2/2) dans le pire des cas où la chaîne contient de très longues chaînes de caractères identiques (ou seulement un caractère unique répété)
MISE À JOUR
Afin de minimiser l'impact des longues chaînes de caractères identiques, l'ordre des positions centrales des palindromes potentiels pourrait suivre un modèle de recherche binaire. Le générateur binRange () ci-dessous peut être utilisé pour remplacer range(1,len(s)-1)
par binRange(1,len(s)-1)
dans la boucle principale. Cela garantira que les palindromes plus longs sont trouvés précocement et que les palindromes plus courts peuvent être court-circuités dans les itérations suivantes.
s = "forgeeksskeegfor" from os import path longest = "" for i in range(1,len(s)-1): if min(i,len(s)-i)*2+1 <= len(longest): continue for odd in [1,0]: if s[i+odd] != s[i-1]: continue halfSize = len(path.commonprefix([s[i+odd:],s[:i][::-1]])) if 2*halfSize + odd > len(longest): longest = s[i-halfSize:i+halfSize+odd];break print(longest) # geeksskeeg
Il existe un moyen simple, cette fonction peut vous aider:
def longest_palindrome(text): text = text.lower() longest = "" for i in range(len(text)): for j in range(0, i): chunk = text[j:i + 1] if chunk == chunk[::-1]: if len(chunk) > len(longest): longest = chunk return longest print(longest_palindrome("forgeeksskeegfor"))
En supposant qu'une sous-chaîne peut contenir 1 caractère (cela peut être facilement modifié dans le conditionnel de vérification de la longueur) et qu'il pourrait y avoir plusieurs chaînes les plus longues avec la même longueur:
def longest_substring(string): longest = "" for i in range(len(string)): for j in range(i + 1, len(string) + 1): sub = ''.join(string[i:j]) if str(sub) == str(sub)[::-1]: if len(sub) > len(longest): longest = sub return longest
geeksforgeeks.org/longest-palindromic-substring-set-2 Parcourez ceci si vous avez des doutes, demandez