如何找到字符串中括号和括号的最大有效序列? [英] How do I find largest valid sequence of parentheses and brackets in a string?

问题描述

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

So I have a script I need to write and one of the largest problems boils down to finding the largest valid subsequence within a string. So I have something like

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

作为输入，我需要返回

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

作为输出.

我已经尝试过使用像栈一样的结构，就像您只是用括号将其括起来一样，但是还无法找出可行的方法.我希望使用python解决方案，但是任何人都可以提供的任何指导都可以提供帮助，无论使用哪种语言.理想情况下，效率应该优于n ^ 2，因为我可以想到使用此

I have tried using a stack like structure like you would do if it was just parentheses but haven't been able to figure out something that works. I'd prefer a solution in python but any guidance anyone can offer will help regardless of language. The efficiency should ideally be better than n^2 since I can think of an O(n^2) solution using this How to find validity of a string of parentheses, curly brackets and square brackets? and just trying it on different substrings

推荐答案

可以使用动态编程来解决.遍历记录从每个索引结束的最长有效匹配的数组.如果您有索引i的最长匹配，那么很容易找到索引i + 1的最长匹配:向后跳过索引i的最长匹配，然后查看周围的字符是否匹配开/括号.然后，将最长的匹配项也添加到该匹配项的左侧(如果有的话).

This can be solved using dynamic programming. Go through the array recording the longest valid match ending from each index. If you've got the longest match for index i, then it's easy to find the longest match for index i+1: skip backwards the longest match for index i, and then see if the characters surrounding that are matching open/close brackets. Then add the longest match to the left of that too, if any.

以下是一些计算此内容的Python代码:

Here's some Python code that computes this:

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).

It's O(n) in time and space.

这篇关于如何找到字符串中括号和括号的最大有效序列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！