Как найти наибольшую допустимую последовательность скобок и скобок в строке?

Итак, у меня есть script Мне нужно написать, и одна из самых больших проблем сводится к поиску самой большой допустимой подпоследовательности внутри строки. Поэтому у меня есть что-то вроде

"()(({}[](][{[()]}]{})))("

в качестве ввода, и мне нужно будет вернуть

"[{[()]}]{}"

в качестве вывода.

Я пробовал использовать стек, подобный структуре, как если бы вы были в скобках, но не смогли выяснить, что работает. Я бы предпочел решение на питоне, но любое руководство, которое может предложить, поможет независимо от языка. Эффективность в идеале должна быть лучше, чем n ^ 2, так как я могу думать о решении O (n ^ 2), используя этот Как найти правильность строки круглых скобок, фигурных скобок и квадратных скобок? и просто пробовать его на разных подстроках

3 ответа

Это можно решить с помощью динамического программирования. Пройдите через массив, записывающий самый длинный действительный матч, заканчивающийся от каждого индекса. Если у вас самое длинное совпадение для индекса i, то легко найти самое длинное соответствие для индекса я + 1: пропустить назад самое длинное соответствие для индекса i, а затем посмотреть, соответствуют ли окружающие символы подходящим скобкам открытия/закрытия. Затем добавьте самое длинное совпадение слева от него, если оно есть.

Здесь приведен код Python, который вычисляет это:

def longest_valid(s): match = [0] * (len(s) + 1) for i in xrange(1, len(s)): if s[i] in '({[': continue open = '({['[')}]'.index(s[i])] start = i - 1 - match[i - 1] if start < 0: continue if s[start] != open: continue match[i] = i - start + 1 + match[start - 1] best = max(match) end = match.index(best) return s[end + 1 - best:end + 1]
print longest_valid("()(({}[](][{[()]}]{})))(")
print longest_valid("()(({}[]([{[()]}]{})))(")
print longest_valid("{}[()()()()()()()]")

Это O (n) во времени и пространстве.


Этот ответ использует следующую последовательность ввода в качестве примера. Ожидаемый вывод - это вся строка, кроме последней (.

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

Алгоритм заканчивается, когда нет ничего, что можно было бы развернуть или объединить. Самый длинный ответ - ответ.

Замечания по внедрению:

Я думаю, что вы можете достичь O(n) путем расширения/слияния одной последовательности за раз. Я бы сохранил список последовательностей в двусвязном списке (так что удаление - это операция O(1)). Каждая последовательность будет представлена ​​индексом start и индексом end.

Расширение последовательности включает проверку символов в array[start-1] и array[end+1], а затем, при необходимости, обновление индексов start/end.

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

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


Если вы говорите о произвольной глубине, то здесь может обратиться: Регулярное выражение для обнаружения циклов С++ for и while с концевой двоеточием

Если мы говорим о конечной глубине, Regex может быть вашим другом (вы можете проверить производительность)

Кажется, что вы ищете:

  • литеральная квадратная скобка
  • куча символов, которые не являются конечными скобками
  • закрыть скобку
  • открытая скобка
  • все символы до последней скобки
  • закрыть скобку

так, язык-агностик что-то вроде:

\[[^]]*\{.*\}

это можно использовать с re.compile с Python, но на самом деле это может быть любой язык. Так как. * (Любые char) и [^]] (неконцевая квадратная скобка), вы можете использовать w + или d + для слова/цифры или другого короткого слова Regex, чтобы уточнить решение и ускорить процесс.

licensed under cc by-sa 3.0 with attribution.