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

Question

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

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

作为输入，我需要返回

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

作为输出。

我尝试过使用类似堆栈的结构，就像您在只是括号时所做的那样，但无法找出有效的方法。我更喜欢 python 中的解决方案，但任何人都可以提供的任何指导都会有所帮助，无论语言如何。理想情况下，效率应该比 n^2 更好，因为我可以使用这个How to find valid of a string of括号、大括号和方括号？想到 O(n^2) 解决方案。只是在不同的子字符串上尝试

Answer 1

这可以使用动态规划来解决。遍历记录从每个索引结束的最长有效匹配的数组。如果您已经获得了索引 i 的最长匹配，那么很容易找到索引 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)。