trouver la plus longue sous-chaîne de lettres dans l'ordre alphabétique dans une chaîne donnée

Question

Lors de l'exécution de mon code pour la tâche donnée, je continue d'obtenir la plus longue chaîne plus la lettre suivante dans l'itération. Par exemple, si j'utilise

s = 'azcbobobegghakl' 

J'obtiendrai "beggha" comme la plus longue chaîne, lorsque la réponse est censée être "beggh". Ce même bug se produit pour toutes les chaînes de lettres aléatoires que j'ai essayé.

J'ai compris que la lettre supplémentaire est ajoutée après l'instruction "result + = letters", mais je ne suis pas sûr de savoir comment la réparer. Voici mon code:

s = 'azcbobobegghakl' 
result = [] 
final = [] 
for letters in s: 
    result += letters 
    if result == sorted(result) and len(result) >= len(final): 
     final=result 
    elif result != sorted(result): 
     result = [result[len(result)-1]] 
print "".join(final) 

Answer 1

Le problème ici est que result et final pointent vers la même liste. Vous pensez probablement que += va créer une nouvelle liste lorsque vous émettez result += letters, mais il ne sera pas:

>>> x = [1,2] 
>>> y = x 
>>> x += [3] 
>>> x 
[1, 2, 3] 
>>> y 
[1, 2, 3] 
>>> x is y 
True 

Cependant, lorsque vous utilisez x = x + [3]:

>>> x = [1,2] 
>>> y = x 
>>> x = x + [3] 
>>> x 
[1, 2, 3] 
>>> y 
[1, 2] 
>>> x is y 
False 

Pour une explication de ce comportement , voir this question. C'est ce qui se passe dans votre boucle for (edit: de votre code d'origine) lorsque letters est le dernier caractère a dans votre chaîne:

1. au début, final et result les deux vers ['b', 'e', 'g', 'g', 'h'].
2. après result += 'a'final et result tous deux pointent vers ['b', 'e', 'g', 'g', 'h', 'a'].
3. maintenant le bloc elif est entré et le résultat pointe vers une nouvelle liste ['a'], tandis que final pointe toujours vers ['b', 'e', 'g', 'g', 'h', 'a'].
4. final ne sera jamais mis à jour à nouveau après cette

Par conséquent, votre code d'origine (avant édita) peut être fixé en changeant

result += letters

à

result = result + [letters]:

s = 'azcbobobegghakl' 
result = [] 
final = [] 
for letters in s: 
    result = result + [letters]   
    if result == sorted(result) and len(result) >= len(final): 
     final=result    
    elif result != sorted(result): 
     result = [result[len(result)-1]]   

print(final) 

Answer 2

Vous avez quelques objets à traiter. La première est que lorsque vous utilisez ...

final = result 

Ceci n'attribue pas seulement les valeurs en résultat à la finale. Il pointe la variable 'final' vers l'adresse mémoire contenant la liste que 'result' pointe également vers. Alors, si le résultat est modifié, il en va de même pour le résultat final. Pour affecter les valeurs dans le résultat, utilisez ...

final = result[:] 

qui vous donnera les valeurs d'une tranche de la liste du début à la fin. Ou vous pouvez utiliser ...

final = list(result) 

Après cette modification, vous devrez supprimer la comparaison de longueur dans votre instruction elif.

Code Modifié:

s = 'azcbobobegghakl' 

result = [] 
final = [] 

for letters in s: 
    result += letters 
    if result == sorted(result) and len(result) >= len(final): 
     final = list(result) 
    elif result != sorted(result): 
     result = [result[len(result)-1]] 
print "".join(final)