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

Я заканчиваю курс «Введение в информатику и программирование с использованием Python» и застрял на неделе 1: основы Python — набор задач 1 — задача 3.

Проблема спрашивает:

Предположим, что s — это строка символов нижнего регистра.

Напишите программу, которая выводит самую длинную подстроку s, в которой буквы расположены в алфавитном порядке. Например, если s = 'azcbobobegghakl', ваша программа должна напечатать

Самая длинная подстрока в алфавитном порядке: beggh

В случае ничьей выведите первую подстроку. Например, если s = 'abcbcd', ваша программа должна напечатать*

Самая длинная подстрока в алфавитном порядке: abc

Есть много сообщений о переполнении стека, где люди просто ищут или дают код в качестве ответа. Я хочу понять концепцию кода, так как я новичок в программировании и хочу лучше понять основы

Я нашел следующий код, который, кажется, отвечает на вопрос. Я понимаю основную концепцию цикла for, но мне трудно понять, как их использовать (циклы for) для поиска алфавитных последовательностей в строке

Может кто-нибудь, пожалуйста, помогите мне понять концепцию использования циклов for таким образом.

s = 'cyqfjhcclkbxpbojgkar'

lstring = s[0]
slen = 1

for i in range(len(s)):
    for j in range(i,len(s)-1):
            if s[j+1] >= s[j]:
                    if (j+1)-i+1 > slen:
                        lstring = s[i:(j+1)+1]
                        slen = (j+1)-i+1
            else:
                        break

print("Longest substring in alphabetical order is: " + lstring)

python for-loop concept
person Pete Smyth    schedule 31.03.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Давайте рассмотрим ваш код шаг за шагом.

Сначала мы предполагаем, что первый символ образует самую длинную последовательность. Что мы сделаем, так это попробуем улучшить это предположение.

s = 'cyqfjhcclkbxpbojgkar'

lstring = s[0]
slen = 1

Затем первый цикл выбирает некоторый индекс i, это будет началом последовательности. Оттуда мы проверим все существующие последовательности, начиная с i, перебирая возможный конец последовательности с помощью вложенного цикла.

for i in range(len(s)): # This loops over the whole string indices
    for j in range(i,len(s)-1): # This loops over indices following i

Эти вложенные циклы позволят нам проверять каждую подпоследовательность, выбирая каждую комбинацию i и j.

Первый оператор if предназначен для проверки того, является ли эта последовательность возрастающей. Если это не так, мы прерываем внутренний цикл, так как эта последовательность нас не интересует.

if s[j+1] >= s[j]:
    ...
else:
    break

Наконец, нам нужно проверить, лучше ли текущая последовательность, которую мы рассматриваем, чем наше текущее предположение, сравнив ее длину с slen, что является нашим лучшим предположением.

if (j+1)-i+1 > slen:
    lstring = s[i:(j+1)+1]
    slen = (j+1)-i+1

Улучшения

Обратите внимание, что этот код не является оптимальным, поскольку он без необходимости проходит по вашей строке несколько раз. Вы можете реализовать более эффективный подход, который проходит по строке только один раз, чтобы восстановить все увеличивающиеся подстроки, а затем использует max для выбора самой длинной.

s = 'cyqfjhcclkbxpbojgkar'

substrings = []

start = 0
end = 1
while end < len(s):
    if s[end - 1] > s[end]:
        substrings.append(s[start:end])
        start = end + 1
        end = start + 1
    else:
        end += 1

lstring = max(substrings, key=len)

print("Longest substring in alphabetical order is: " + lstring)

Список substrings выглядит после цикла while следующим образом: ['cy', 'fj', 'ccl', 'bx', 'bo', 'gk']

Из них max(..., key=len) выбирает самый длинный.

person Olivier Melançon    schedule 31.03.2018
comment
Спасибо @olivierm. Ваше четкое объяснение помогло мне понять, что делают вложенные циклы и сравнения. Ваше здоровье - person Pete Smyth; 31.03.2018