Recherche de la plus longue sous-chaîne alphabétique dans une chaîne plus longue

Question

J'ai besoin d'un code pour trouver la plus longue sous-chaîne alphabétique dans une chaîne. Ce est le code que je utilise:

letter = s[0]  
best = ''   
for n in range(1, len(s)):  
    if len(letter) > len(best): 
     best = letter 
    if s[n] >= s[n-1]: 
     letter += s[n]  
    else:      
     letter = s[n] 

Il fonctionne la plupart du temps, mais parfois il donne les mauvaises réponses et je suis confus pourquoi il ne fonctionne que parfois. par exemple lorsque:

s = 'maezsibmhzxhpprvx'

Il a dit que la réponse était "hpprv" alors qu'il aurait dû être "hpprvx".

Dans un autre cas, lorsque

s = 'ysdxvkctcpxidnvaepz'

Il a donné la réponse "CPX", quand il aurait dû être "aepz".

Que se passe-t-il ici?

Answer 1

Votre routine était presque ok, voici une petite comparaison entre le vôtre, fixe un et l'autre solution possible à votre problème:

def buggy(s): 
    letter = s[0] 
    best = '' 
    for n in range(1, len(s)): 
     if len(letter) > len(best): 
      best = letter 
     if s[n] >= s[n - 1]: 
      letter += s[n] 
     else: 
      letter = s[n] 

    return best 


def fixed(s): 
    letter = s[0] 
    best = '' 
    for n in range(1, len(s)): 
     if s[n] >= s[n - 1]: 
      letter += s[n] 
     else: 
      letter = s[n] 

     if len(letter) > len(best): 
      best = letter 

    return best 


def alternative(s): 
    result = ['' for i in range(len(s))] 
    index = 0 

    for i in range(len(s)): 
     if (i == len(s) - 1 and s[i] >= s[i - 1]) or s[i] <= s[i + 1]: 
      result[index] += s[i] 
     else: 
      result[index] += s[i] 
      index += 1 

    return max(result, key=len) 


for sample in ['maezsibmhzxhpprvx', 'ysdxvkctcpxidnvaepz']: 
    o1, o2, o3 = buggy(sample), fixed(sample), alternative(sample) 
    print "buggy={0:10} fixed={1:10} alternative={2:10}".format(o1, o2, o3) 

Comme vous pouvez le voir dans votre version de l'ordre de la boucle intérieure conditionnelle est pas bon, vous devez déplacer le premier conditionnel à la fin de la boucle.

Answer 2

Vous devez déplacer cette vérification

if len(letter) > len(best): 
    best = letter 

après le reste de la boucle

Answer 3

La logique est presque correct, sauf que si letter pousse sur la dernière itération de la boucle (quand n == len(s) - 1), best n'est pas changé cette dernière fois. Vous pouvez insérer une autre partie best = letter après la boucle, ou repenser soigneusement la structure du programme afin de ne pas vous répéter.