Этот ответ использует следующую последовательность ввода в качестве примера. Ожидаемый вывод - это все строки, за исключением последних (
.
Input: ()(({}[]([{[()]}]{})))(
Output:()(({}[]([{[()]}]{})))
Шаг 1 - найти семена в строке. Семя представляет собой согласованный набор символов: ()
, []
, или {}
. Я дал каждому семени численное значение, чтобы помочь читателю визуализировать семена.
()(({}[]([{[()]}]{})))(
11 2233 44 55
Шаг 2 является расширить семена в последовательности. Последовательности представляют собой вложенный набор символов: например. [{[()]}]
. Поэтому, начиная с семени, работайте наружу, проверяя соответствие соответствующих символов. Поиск заканчивается с несоответствием или в начале или в конце строки. В этом примере только семя 4 заключает в себя соответствующие символы, поэтому расширяется только семя 4.
()(({}[]([{[()]}]{})))(
11 2233 4444444455
Шаг 3 состоит в объединить смежные последовательности. Обратите внимание, что может быть два или более смежных последовательностей, но в этом примере есть две смежные последовательности в двух местах
()(({}[]([{[()]}]{})))(
11 2222 4444444444
Повторите шаг 2, рассматривая комбинированные последовательности как семена. В этом примере последовательность 4 заключена в соответствующие круглые скобки, поэтому последовательность 4 расширяется.
()(({}[]([{[()]}]{})))(
11 2222444444444444
Повторите шаг 3, объединить последовательности
()(({}[]([{[()]}]{})))(
11 2222222222222222
Повторите шаг 2, расширить
()(({}[]([{[()]}]{})))(
1122222222222222222222
И объединить еще один раз
()(({}[]([{[()]}]{})))(
1111111111111111111111
Алгоритм заканчивается, когда нет ничего оставлять для расширения, или c ombine. Ответ - самая длинная последовательность.
Примечание по реализации:
Я думаю, что вы можете достичь O(n)
пути расширения/слияния одной последовательности в то время. Я бы сохранил список последовательностей в двусвязном списке (поэтому удаление - операция O(1)
). Каждая последовательность будет представлена индексом start
и индексом end
.
Расширение последовательности включает проверку символов на array[start-1]
и array[end+1]
, а затем обновление индексов start
/end
в зависимости от обстоятельств.
Слияние предполагает проверку следующей и предыдущей последовательностей в связанном списке. Если последовательности можно объединить, то одна последовательность обновляется, чтобы охватить весь диапазон, а другая удалена.
Как только последовательность будет расширена или объединена как можно больше, перейдите к следующей последовательности в списке. Поскольку эта новая последовательность расширяется/объединяется, она может в конечном итоге вернуться к предыдущей последовательности. Следовательно, после первоначального создания двусвязного списка семян один проход через связанный список должен быть достаточным для расширения/слияния всех последовательностей. Затем нужно пройти второе, чтобы найти самую длинную последовательность, оставшуюся от связанного списка.
Мне кажется, что правильным ответом будет все, кроме последнего '(', или я что-то не понимаю о вопросе? – user3386109
Нет, вы этого не сделали.Я просто глуп. Отредактировано – user1984974
На самом деле, мне понравилась входная последовательность, я просто хотел убедиться, что мы договорились о выходной последовательности :) – user3386109