Python-сообщество

Добрый день,
С регулярными выражениями мало сталкивалась, поэтому очень нужна помощь.
Есть строка размером N составленная из k элементов.
Нужно найти минимальный отрезок в строке из N элементов, с вхождением всех k возможных элементов не менее 1 раза
Например:

Можно ли решить задачу через регулярные выражения и как это сделать?
Буду очень благодарна за помощь

Отредактировано NK (Май 8, 2016 16:08:52)

NK
Можно ли решить задачу через регулярные выражения и как это сделать?

Через регулярные выражение её не решишь. (Можно ерунду только написать, далёкую от элегантного решения.)

Отредактировано py.user.next (Май 8, 2016 16:52:09)

py.user.next

Спасибо за ответ! Подскажите, пожалуйста, хотя бы направление, как такую задачу решать?

NK
как такую задачу решать?

Вообще, надо составить юнит-тесты. Это чтобы не пропереться с какой-нибудь последовательностью. А то можно алгоритм написать, а он какую-нибудь редкую последовательность неправильно обработает. Чтобы его изменить, надо будет проверять все последовательности заново. И так каждый раз при любой ошибке.

Ну, допустим, мы их составили. Дальше само решение:
Допустим, у нас исходные данные:
Тогда в ответе будет вся эта строка.

Нужно сделать пустое множество и при проходе по строке от её начала заполнять его походящими элементами. Когда множество заполнится всеми элементами, надо всю строку, которую рассматривали, сохранить. Затем надо повторить процедуру со второго символа. Когда множество заполнится, нужно сравнить по длине новую строку со строкой из предыдущего шага. Если новая строка короче, то её сохранить вместо предыдущей. Затем повторить всё с третьего символа. Когда дойдёшь до последнего символа, у тебя останется сохранённой самая короткая строка, содержащая все символы.

py.user.next

Спасибо! Все супер, написала, работает