Trouvez le palindrome d'une chaîne en utilisant python

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.

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