Самая длинная алфавитная подстрока - с чего начать

Question

Я работаю над проблемой "самой длинной алфавитной подстроки" из популярного курса MIT. Я прочитал много информации на SO о том, как ее кодировать, но я действительно изо всех сил пытаюсь сделать скачок концептуально. Упражнения для пальцев, предшествовавшие ему, были не слишком сложными. Мне было интересно, если кто-нибудь знает какой-либо материал там, который действительно сломал бы решение проблем, используемых в этой проблеме. Я пытался достать ручку и бумагу, и я просто заблудился. Я вижу людей, использующих своего рода "счетчики" или строки, которые содержат "самую длинную подстроку на данный момент", и когда я смотрю на чье-то решение, я могу понять, что они сделали со своим кодом, но если я пытаюсь синтезировать что-то свое, просто не щелкаю.

Я даже взял перерыв в курсе и попробовал учиться по другим книгам, но я продолжаю возвращаться к этой проблеме и чувствую, что мне нужно ее преодолеть. Я думаю, что я борюсь с тем, чтобы сделать шаг от знания некоторых синтаксисов и инструментов Python к реальному использованию этих инструментов для решения проблем или «вычисления».

Прежде чем кто-либо укажет мне на это, я знаю о материалах курса, которые направлены на помощь. Я видел несколько видео, которые сделал один из ТА, которые несколько полезны, но на самом деле он этого не сломал. Я чувствую, что мне нужно спрограммировать это с кем-то или как ... сесть перед доской и попросить кого-нибудь пройти меня шаг за шагом и ответить на каждый глупый вопрос, который у меня возникнет.

Для справки, проблема заключается в следующем:

Предположим, s - это строка строчных букв.

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

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

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

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

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

s = 'azcbobobegghakl'

current = s[0]
longest = s[0]

for letter in range(0, len(s) -1):
    if s[letter + 1] >= s[letter]:
        current.append(s[letter + 1])
        if len(current) > len(longest):
            longest = current
        else:
            current = 

Извините за ошибки форматирования, все еще новичок в этом. Я действительно разочарован этой проблемой.

Answer 1

Один из способов справиться со сложностью реализации, для меня, написать несколько модульных тестов: в какой-то момент, если я не могу понять из "чтения кода", что не так и / или какие части отсутствуют,Мне нравится писать модульные тесты, которые являются «ортогональным» подходом к проблеме (вместо того, чтобы думать «как я могу решить эту проблему?», Я спрашиваю себя «какие тесты я должен написать, чтобы убедиться, что он работает нормально?»).

Затем, запустив тесты, я могу наблюдать за тем, как ведет себя реализация, и пытаться исправить проблемы «один за другим», т. Е. Сосредоточиться на выполнении следующего модульного теста.

Это также способ «вырезания».большая проблема в небольших задачах, о которых легче рассуждать ".

Answer 2

Как правило, проще создать список всех возможностей из входных данных, а затем отфильтровать результаты на основе необходимой дополнительной логики.Например, при поиске самых длинных подстрок могут быть найдены все подстроки входных данных, а затем сохраняются только элементы, которые являются действительными последовательностями:

def is_valid(d):
  return all(d[i] <= d[i+1] for i in range(len(d)-1))

def longest_substring(s):
  substrings = list(filter(is_valid, [s[i:b] for i in range(len(s)) for b in range(len(s))]))
  max_length = len(max(substrings, key=len)) #this finds the length length of the longest valid substring, to be used if a tie is discovered
  return [i for i in substrings if len(i) == max_length][0]

l = [['abcbcd', 'abc'], ['azcbobobegghakl', 'beggh']]
for a, b in l:
  assert longest_substring(a) == b

print('all tests passed')

Вывод:

all tests passed

Answer 3

Если вы боретесь с концепциями и логикой, стоящими за решением этой проблемы, я бы порекомендовал, пожалуй, немного отступить и перейти к более простым учебникам по кодированию и интерактивным упражнениям. Вам также может понравиться экспериментировать с JavaScript, где было бы проще с самого начала проявить творческий подход, создав фрагменты и / или веб-страницы, с которыми можно немедленно взаимодействовать в браузере. Тогда, когда вы получите больше забавного словарного запаса под вашим поясом, его алгоритмическая часть будет казаться более знакомой и естественной. Я также думаю, что если вы будете руководствоваться собственным творчеством и воображением, это может стать очень мощным процессом обучения.

Давайте пока забудем об алфавитной части. Представьте, что у нас есть пакет с буквами, которые мы вытаскиваем по одному, не зная, что будет дальше, и мы должны записать самый длинный пробег R с подряд. Как бы вы это сделали? Попробуем описать процесс словами, затем псевдокодом.

Мы сохраним контейнер для самого длинного пробега, который мы когда-либо видели, и еще один для проверки текущего пробега. Мы вытягиваем буквы до тех пор, пока не достигнем двух R с подряд, и поместим их в «текущий» контейнер. Следующая буква не является R, что означает, что наш пробег закончился. Прогон «самый длинный на данный момент» пуст, поэтому мы наливаем в него «текущий» контейнер и продолжаем. Следующие четыре буквы не R с, поэтому мы просто игнорируем их. Затем мы получаем один R, который мы помещаем в «текущий», а затем H. Наш пробег снова закончился, но на этот раз наш R в «текущем» был меньше, чем два, которые мы уже имеем в «самом длинном на данный момент», поэтому мы оставляем их и пустым «текущий».

Мы получаем A, B и C, а затем серию из пяти R с, которую мы помещаем в «текущий» контейнер один за другим. Наша сумка теперь содержит последнюю букву, T. Мы видим, что наш цикл снова закончился, и что у «текущего» контейнера больше, чем у «самого длинного» контейнера, поэтому мы выливаем «самый длинный» и заменяем его содержимое на пять R с в «текущем». Вот и все, мы нашли самый длинный пробег R с в сумке. (Если бы у нас было больше прогонов, каждый раз, когда один из них заканчивался, мы выбирали, заменять ли содержимое «самым длинным на данный момент».)

в псевдокоде:

// Initialise
current <- nothing
longest <- nothing

for letter in bag:
  if letter == 'R':
    add 'R' to current
  else:
    if there are more letters
    in current than longest:
      empty longest and pour
      in letters from current
    otherwise:
      empty current to get ready
      for the next possible run

Теперь алфавитное условие немного усложняет наше условие. Нам нужно будет отследить самое последнее письмо, помещенное в «текущее», и для продолжения пробега не будет видно другого того же письма, которое имеет значение. Скорее, следующая буква должна быть «большей» (лексикографически), чем последняя, ​​которую мы поместили в текущую; в противном случае цикл заканчивается, и мы выполняем проверку количества на «самый длинный».

Answer 4

Вы почти в своем примере, просто нужно немного подправить

s = 'azcbobobegghakl'

longest = [s[0],]  # make them lists so we can manipulate them (unlike strings)
current = [s[0],]

for letter in range(0, len(s) -1):
    if s[letter + 1] >= s[letter]:
        current.append(s[letter + 1])
        if len(current) > len(longest):
            longest = current
    else:
        current = [s[letter+1],]  # reset current if we break an alphabetical chain

longest_string = ''.join(longest)  # turn out list back into a string

вывод longest_string:

'beegh'