如何在字符串中找到最大的有效括号序列？

Question

所以我需要编写一个脚本，最大的问题之一归结为在字符串中找到最大的有效子序列。所以我有类似

的东西

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

作为输入，我需要 return

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

作为输出。

我已经尝试过使用类似堆栈的结构，如果它只是括号，您会这样做，但一直无法找出可行的方法。我更喜欢 python 中的解决方案，但无论语言如何，任何人都可以提供的任何指导都会有所帮助。理想情况下，效率应该比 n^2 更好，因为我可以想到一个 O(n^2) 解决方案，使用这个 How to find validity of a string of parentheses, curly brackets and square brackets? 并在不同的子字符串上尝试它

Answer 1

如果您谈论的是任意深度，Franks anser 在这里可能适用： Regular expression to detect semi-colon terminated C++ for & while loops

如果我们谈论的是有限深度，正则表达式可能是你的朋友（你可能想检查性能）

您似乎在寻找：

文字方括号
一堆不是结束括号的字符
右括号
左括号
直到最后一个右括号的所有字符
右括号

所以，与语言无关的是这样的：

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

这可以与 re.compile 和 Python 一起使用，但实际上它可以是任何语言。由于假定 .*（任何字符）和 [^]]（非结束方括号），您可以将 w+ 或 d+ 用于 word/digit 或其他 Regex 速记来改进解决方案并加快速度。

Answer 2

本回答以下列输入序列为例。预期输出是除最后一个 (.

之外的所有字符串

Input:  ()(({}[]([{[()]}]{})))(
Output: ()(({}[]([{[()]}]{})))

第一步是找到字符串中的种子。种子是一组匹配的符号：()、[] 或 {}。我给每个种子一个数值，以帮助 reader 可视化种子。

()(({}[]([{[()]}]{})))(
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

当没有任何东西可以扩展或组合时，算法结束。最长的序列就是答案。

实施说明：

我认为您可以通过 expanding/merging 一次一个序列来实现 O(n)。我会将序列列表保存在双向链表中（因此删除是一个 O(1) 操作）。每个序列将由一个 start 索引和一个 end 索引表示。

扩展序列涉及检查 array[start-1] 和 array[end+1] 处的符号，然后适当更新 start/end 索引。

合并涉及检查链表中的下一个和上一个序列。如果可以合并序列，则更新一个序列以覆盖整个范围，并删除另一个。

一旦一个序列尽可能 expanded/merged，就移至列表中的下一个序列。由于这个新序列是 expanded/merged，它最终可能会返回到先前的序列。因此，在最初创建种子的双向链表后，一次遍历链表应该足以 expand/merge 所有序列。然后第二次遍历链表的任何剩余部分以找到最长的序列。

Answer 3

这可以使用动态规划来解决。遍历记录从每个索引结束的最长有效匹配项的数组。如果你有索引 i 的最长匹配，那么很容易找到索引 i+1 的最长匹配：向后跳过索引 i 的最长匹配，然后查看周围的字符是否匹配 open/close括号。然后将最长的匹配也添加到它的左侧，如果有的话。

这里有一些 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) space。

Answer 4

这是一个老问题，但我想提供一种 O(n) 方法，该方法单次遍历字符并使用堆栈跟踪匹配项。当找到连续的平衡组时，它会将长度汇总到前一个嵌入组。

from collections import deque
def balanced(s):
    groups = {"(":")", "[":"]", "{":"}"}
    result = ""
    starts = deque([["",0,0]])              # stack of [closingChar,position,width]
    for i,c in enumerate(s):
        if c in groups:
            starts.append([groups[c],i,1])  # stack opening groups
        elif c != starts[-1][0]:
            starts = [["",i+1,0]]           # unmatched open/close, clear stack
        else:
            _,p,w   = starts.pop()                     # close group
            if not starts: starts.append(["",p,0])     # maintain ungrouped baseline
            starts[-1][2] = w = starts[-1][2] + w + 1  # roll up group size
            if w-w%2>len(result):                      # track longest
                result = s[starts[-1][1]+w%2:][:w-w%2] # w%2 handles grouped/ungrouped
    return result

输出：

balanced("()(({}[](][{[()]}]{})))(") # [{[()]}]{}

balanced("()(({}[]([{[()]}]{})))(")  # ()(({}[]([{[()]}]{})))

balanced("{}[()()()()()()()]")       # {}[()()()()()()()]

balanced("{[([](){}})]")             # [](){}

如何在字符串中找到最大的有效括号序列？

How do I find largest valid sequence of parentheses and brackets in a string?

python

algorithm

stack

dynamic-programming

parentheses