1

Нужна помощь. Помогите нащупать правильный алгоритм решения задания.

Задание:

Дана строка s = 'pqrsxdef' (строка может быть любой) в этой строке есть две подстроки, которые сохраняют последовательность в алфавите: pqrs и def. Нужно найти их, перевернуть и "вставить обратно" так чтобы получилась "srqpxfed"

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

Пробовал:

from icecream import ic # такой вывод мне нравится больше чем стандартный print
from string import ascii_lowercase

for i in range(len(s)):
    if s[i:] in ascii_lowercase:
        ic(s[i:])
        ic(s[:i] + s[i:][::-1])
        break 

но очевидно, что это решение не подходит...

Подскажите "в какую сторону" думать?

нарезать s на все возможные комбинации и проверять их на наличие в ascii_lowercase? нарезать ascii_lowercase на все возможные комбинации и проверить их наличие в s? но это же будет долго, нудно и не оптимально.

как тогда?

3 ответа 3

3

gen сверяет пары последовательных символов. Если они не по порядку в алфавите, предыдущий фрагмент строки выдаётся наружу. revolver все фрагменты переворачивает и склеивает в строку:

import string


def pairs(s):
    """ 'abcd' -> ('a', 'b'), ('b', 'c'), ('c', 'd') """
    it = iter(s)
    next(it, None)
    return zip(s, it)


# {('a', 'b'), ('b', 'c'), ..., ('x', 'y'), ('y', 'z')}
alphabet_pairs = set(pairs(string.ascii_lowercase))


def revolver(s):

    def gen():
        """ 'pqrsxdef' -> 'pqrs', 'x', 'def' """
        i = 0
        for j, p in enumerate(pairs(s), start=1):
            if p not in alphabet_pairs:
                yield s[i:j]
                i = j
        yield s[i:]

    return ''.join(s[::-1] for s in gen())


print(revolver(input()))
$ echo pqrsxdef | python revolver.py
srqpxfed
2
  • Идея со словарём хорошая. И коды символов не нужно брать )
    – CrazyElf
    27 авг в 8:58
  • @CrazyElf, переделал словарь на множество пар. 27 авг в 9:09
2

Вы пытаетесь пойти простым путём, но когда вы делаете срез и проверяете его через in на вхождение, получается сложность O(n2). А если делать комбинации (а это уже O(n2)) и проверять их через in на вхождение, то это вообще O(n3) получится.

Судя по всему, тут нужно думать так.

  • Что нам нужно найти? Возрастающие (на 1) последовательности букв.
  • Что такое возрастающая (на 1) последовательность букв? Это последовательность, в которой код следующего символа на 1 больше кода предыдущего символа.
  • Как получить сложность алгоритма O(n)? Нужно идти по строке последовательно в один проход и анализировать её.

Таким образом, ближе к алгоритму:

  • Будем накапливать найденные последовательности вида (индекс начала, индекс конца [может ещё +1 чтобы сразу готовый срез был]) в списке sequences.
  • Заведём булеву переменную in_sequence, показывающую, копим мы уже последовательность или ещё не нашли ничего.
  • Ну и дальше нужно идти по строке, смотреть, отличается ли код следующего символа на 1 от предыдущего (в бОльшую сторону) и какое у нас значение in_sequence и обрабатывать 4 возможных получающихся варианта.
  • Запоминать начало последовательности, если найдено её начало. в переменной start.
  • Когда заканчивается очередная последовательность - добавлять её в наш список sequences.
  • Когда закончится разбор строки, ещё раз проверить значение in_sequence и если оно True, то не забыть добавить последнюю последовательность в наш список.
  • В конце алгоритма идём по списку sequences, выводим неизменные части строки (это с конца предыдущей последовательности до начала новой) и перевёрнутые - это сама очередная последовательность, перевёрнутая.
  • Не забыть вывести конец строки от конца последней последовательности.

Как вариант - можно скидывать в список и последовательности и не-последовательности (с каким-то признаком). Потом проще будет выводить что получилось.

0

Спасибо за помощь и подсказки, друзья.

CrazyElf - это тот случай когда после подсказки хлопаешь себя по лбу и говоришь: "точно, ну как я сам до этого не додумался"

Stanislav Volodarskiy - красивое и изячное решение, до которого я не додумался, спасибо.

Мое решение было таким:

from string import ascii_lowercase as abc

def solution(s):
    word = s[0]
    ans = []
    for i in s[1:]:
        if word + i in abc:
            word += i
        else:
            ans += [word]
            word = i

    ans = ans + [word]


    result = ''
    for i in ans:
        if len(i) > 1 and i in abc:
            result += i[::-1]
        else:
            result += i

    return result 

Не такое красивое и изящное, громоздкое и не оптимизированное, но тоже подошло...

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.