首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >最长的平衡括号子序列

问最长的平衡括号子序列
EN

Stack Overflow用户
提问于 2014-10-30 01:46:28
回答 2查看 6.8K关注 0票数 2

我正在试图解决我前面问过的problem的一个变体:

给定一个括号字符串(长度为1,000,000)和一个范围查询列表,为每个<= 100,000次查询在每个范围内查找最长的子序列。

我发现了这个other,所以这个问题是相似的,但是只有一个O(N^3)算法。

我认为表单dp[i, j] = longest balanced subsequence in [i .. j]的DP解决方案应该可以工作,因为一旦计算完毕,就可以通过查询DP表来回答所有的范围查询。但是,即使是O(N^2)解也会由于输入字符串长度较大而超过时间限制。

此外,使用堆栈跟踪匹配括号的技巧不再直接有效,因为您正在寻找子序列,而不是子字符串。

我有一种方法,我认为可能有效,但不确定:

间隔内平衡括号最长子序列的长度是该间隔内最长的不重叠子串长度的总和。

例如,如果您有字符串

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ) ) ( ( ) ( ( ) ) ) ) ( ( ) )

在间隔0, 8中,平衡括号最长子序列的长度是5,这个长度等于间隔内最长的不重叠子串长度之和:"( )“+ "( )”(())。

这种方法是否总是有效的,还是有更好的方法?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2014-10-30 06:13:48

由于其他人发布了一个答案,下面是对带有O(1)空间的单个查询的一个O(1)答案。保持parens的计数平衡,并指示最后一个打开的和最后一个关闭的paren。直到你已经运行的字符串,扫描在最后一个打开,以找到另一个打开的帕伦。然后从上一次打开和最后一次关闭的最大值向前扫描,以找到下一次关闭的paren。如果以这种方式找到一对,则增加parens的平衡计数。当您到达字符串的末尾时,您将得到正确的计数,即使您不正确地配对父母。

实际上,平衡双亲可能存在多个最大子序列。但是,如果你取平衡父母的任何最大子序列,用左-最可能的开帕伦替换每一个开的帕伦,然后每一个关闭的帕伦替换为最有可能的打开的父本,结果将是你找到的。(留给读者的证明是一项有益的练习。)

这是伪码。

代码语言:javascript
复制
parens = 0
last_open = 0
last_closed = 0
while last_open < len(str) && last_closed < len(str):
    if str[last_open] == ')':
        # We are looking for the next open paren.
       last_open += 1
    elif last_closed < last_open:
       # Start our search for a last closed after the current char
       last_closed = last_open + 1
    elif str[last_closed] == '(':
       # still looking for a close pair
       last_closed += 1
    else:
       # We found a matching pair.
       parens += 1
       last_open += 1
# and now parens has the correct answer.

接下来,我们将面临许多范围查询的挑战。结果表明,快速查询需要O(n)预计算和O(n)空间,而每个范围查询都需要O(log(n))时间。

下面是这个问题的提示。假设我们有两个街区A和B就在一起。其中每一个内部都有一定数量的平衡子序列的双亲,一些额外的打开父母亲可用的权利,和一些额外的关闭父母亲可用的左边。然后,组合块C具有以下内容:

代码语言:javascript
复制
C.balanced = A.balanced + B.balanced + min(A.open, B.close)
C.open = B.open + max(A.open - B.close, 0)
C.close = A.close + max(B.close - A.open, 0)

我留给你们的练习是,找出要预先计算的一组块,以便能够在时间O(log(n))中计算任何块。

票数 6
EN

Stack Overflow用户

发布于 2014-10-30 04:55:02

我将描述一个O(n)解

首先,我们有一个dp[n]数组,对于每个位置i,如果i是近括号),dp[i]将存储最远的位置,这将形成一个以i结尾的有效括号序列。

我们保持一个堆栈,它跟踪开放括号和他们的位置。因此,如果我们遇到一个打开的括号,我们将它连同它的位置一起放入堆栈中,如果我们遇到一个近括号,我们会弹出最后一个打开的括号,并更新dp数组。

  • dp[i] = min (position of open bracket, dp[position of open bracket - 1] ),这将检查开括号之前是否有近括号,如果有,我们改进了dp[i]。

因此,答案将是i - dp[i]之间的最大值

Java代码:

代码语言:javascript
复制
    public static void main(String[] args) {
    String val = "))(()(())))(())";// Which store the parentheses sequence
    int[] dp = new int[val.length()];
    Arrays.fill(dp, -1);

    Stack<Integer> stack = new Stack();
    for (int i = 0; i < val.length(); i++) {
        char c = val.charAt(i);
        if (c == '(')
            stack.push(i);
        else if (!stack.isEmpty()) {
            int v = stack.pop();
            dp[i] = v;
            if (v > 0 && val.charAt(v - 1) == ')')
                if (dp[v - 1] != -1)
                    dp[i] = dp[v - 1];
        }
    }
    int result = 0;
    for (int i = 0; i < val.length(); i++){
        if (dp[i] != -1){
            System.out.println(val.substring(dp[i] , i + 1));

            result = Math.max(result, i - dp[i] + 1);
        }
    }
    System.out.println(result);
}

输出:

代码语言:javascript
复制
()
()
()(())
(()(()))
()
(())
8
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/26643697

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档