Поиск самой длинной алфавитной подстроки в более длинной строке

Question

Мне нужен код, чтобы найти самую длинную алфавитную подстроку в строке (-ах). Это код, я использую:

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] 

Он работает большую часть времени, но иногда это дает неправильные ответы, и я запутался, почему это работает только иногда. например, когда:

S = 'maezsibmhzxhpprvx'

Он сказал, что ответ был "hpprv" в то время как это должно было быть "hpprvx".

В другом случае, когда

S = 'ysdxvkctcpxidnvaepz'

Он дал ответ "CPX", когда оно должно было быть "aepz".

Что здесь происходит?

Answer 1

Ваша рутина была почти нормально, вот немного сравнения между вашим, неподвижной один и другим возможным решение вашей проблемы:

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) 

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

Answer 2

Вы должны переместить эту проверку

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

после остальной части цикла

Answer 3

Логика почти нормально, за исключением того, если letter растет на последней итерации цикла (когда n == len(s) - 1), best не изменяется это последний раз. Вы можете вставить еще одну часть best = letter после цикла или тщательно пересмотреть структуру программы, чтобы вы не повторялись.