在O(n)时间内找到字符串中最长的有效括号序列的长度

Question

我的朋友在面试中遇到了一个问题，被告知有一个O(n)的解决方案。然而，我们两个都想不出来。以下是问题：

有一个字符串只包含括号 ( 和 )，请找出最长的有效括号子串的长度，该子串应该是格式良好的。

例如，对于字符串 ")()())"，最长的有效括号子串是 ()()，长度为 4。

我用动态规划想出来了，但它不是O(n)。有什么想法吗？

public int getLongestLen(String s) {
    if (s == null || s.length() == 0)
        return 0;

    int len = s.length(), maxLen = 0;
    boolean[][] isValid = new boolean[len][len];
    for (int l = 2; l < len; l *= 2)
        for (int start = 0; start <= len - l; start++) {
            if ((s.charAt(start) == '(' && s.charAt(start + l - 1) == ')') && 
                (l == 2 || isValid[start+1][start+l-2])) {
                    isValid[start][start+l-1] = true;
                    maxLen = Math.max(maxLen, l);
                }
        }

    return maxLen;
}

- Bram

---

你听说过计算括号吗？当你对每个(加1并对每个)减1时，就会进行计数。 - n. m.

DP解决方案的反例：任何长度不等于2的幂的有效序列(()()())和任何不能通过将单个括号对添加到另一个有效序列来生成的有效序列((())(()))。 - Leonid Vasilev

Answer 1

我之前做过这个问题，但在压力下想出O(n)的解决方案并不容易。以下是使用栈解决该问题的答案。

   private int getLongestLenByStack(String s) {
    //use last to store the last matched index
    int len = s.length(), maxLen = 0, last = -1;
    if (len == 0 || len == 1)
        return 0;

    //use this stack to store the index of '('
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < len; i++) {
        if (s.charAt(i) == '(') 
            stack.push(i);
        else {
            //if stack is empty, it means that we already found a complete valid combo
            //update the last index.
            if (stack.isEmpty()) {
                last = i;        
            } else {
                stack.pop();
                //found a complete valid combo and calculate max length
                if (stack.isEmpty()) 
                    maxLen = Math.max(maxLen, i - last);
                else
                //calculate current max length
                    maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }

    return maxLen;
}

- David

---

刚刚进行了测试，它能够正常工作！这是一个很棒的解决方案。非常感谢！ - Bram

谢谢您提供的解决方案。我之前遇到了困难，无法弄清楚如何做，即使使用了堆栈也没有发现如何确保在相邻情况下将先前的序列添加到当前序列中。这使问题变得清晰明了。 - Sid

@Sid，我很高兴它能对你有所帮助。 - David

Answer 2

我们需要在一个栈中存储先前起始括号的索引。

我们将栈的第一个元素作为特殊元素推入，如"-1"或任何其他不会出现在索引中的数字。

现在我们遍历字符串，当我们遇到 "(" 括号时，我们将它们推入栈中；否则，当我们遇到 ")" 时，我们首先弹出它们，

如果栈不为空，我们通过将结果（初始化为零）与当前索引和栈顶索引之间的差的最大值来找到到该点的最大有效子串的长度。

否则，如果栈为空，我们推入该索引。

int result=0;
stack<int> s1;
s1.push(-1);
for(int i=0;i<s.size();++i)
{
    if(s[i]=='(')
        s1.push(i);

    else if(s[i]==')')
    {
        s1.pop();

        if(!s1.empty())
            result=max(result,i-s1.top());
        else
            s1.push(i);
    }
}
cout<<result<<endl;

's'是字符串，'s1'是栈。

- Prashant Shubham

---

好的答案，巧妙地使用了 push 和 pop。 - Barkermn01

迄今为止最好且易于理解的答案。 - Akash Chaudhary

Answer 3

你可以通过每个开括号/闭括号分别递增/递减一个 int 变量来计算。将这样有效操作的数量（其中变量不会低于 0）作为当前长度进行跟踪，并将最长的操作记录为 max。

public int getLongestLen(String s) {
    if (s == null || s.length() == 0) {
        return 0;       
    }

    int stack = 0;
    int counter = 0;
    int max = 0;

    for (Character c: s.toCharArray()) {
        if (c == '(') {
            stack++;
        }
        if (c == ')') {
            stack--;
        }
        if (stack >= 0) {
            counter++;
        }
        if (stack < 0) {
            counter = 0;
            stack = 0;
        }
        if (counter > max && stack == 0) {
            max = counter;
        }
    }

    return max;
}

- nbrooks

---

@axiom 我认为“不正确”取决于您对有效括号序列的定义，这在此处并不完全清楚。我使用的是（有些标准的）解释：从0开始（即第一个(），并以0结束。这就是为什么有一个stack==0 结束子句的原因。所以 (() 正确地产生了长度为 0。如果您熟悉Catalan number 问题，那么这将是一条“有效”的山脉——从海平面开始和结束，如这张[图片](http://en.wikipedia.org/wiki/Catalan_number#mediaviewer /File:Mountain_Ranges.png)所示。 - nbrooks

否则，如果您只想跟踪最长的序列直到它变得无效，您可以在该点（在将其重置为0之前）仅获取counter值。如果您感兴趣，我可以展示一下。 - nbrooks

我在这里没有看到任何不清楚的地方。所需的是最长有效括号序列的长度，这只有一个定义。在这个例子中，答案应该是2，因为()是最长有效序列。除非我漏掉了什么，你正在解决一个不同的问题。 - axiom

是的，这是不正确的。它并没有真正回答所提出的问题，而是解决了其他问题。 - Sid

Answer 4

算法：GitHub上的完整代码
1. 添加到堆栈
1.1 初始化为-1，处理没有((的情况
2. 当您看到)时从堆栈中弹出
2.a 如果堆栈大小== 0（无匹配项），则推送当前索引值
2.b 如果堆栈大小> 0（匹配），则通过将顶部值的索引从当前索引中减去来获取最大长度（非常厉害！）

def longestMatchingParenthesis(a):
    pstack = []        #index position of left parenthesis
    pstack.append(-1)  #default value; handles ) without ( and when match adds up to 2!
    stack_size = 1 
    result = 0
    for i in range(0,len(a)):
            if a[i] == '(':
                    pstack.append(i) #Append current index
                    stack_size += 1
            else:    # handle )
                    pstack.pop()
                    stack_size -= 1
                    #determine length of longest match!
                    if stack_size > 0:
                            #difference of current index - index at top of the stack (yet to be matched)
                            result = max(result, i - pstack[-1])
                    else:
                            #stack size == 0, append current index
                            pstack.append(i)
                            stack_size += 1 
    return result

a = ["()()()", "", "((((", "(((()", "(((())(", "()(()" ,"()(())"]
for x in a:
    print("%s = %s" % (x,longestMatchingParenthesis(x)))

#output
()()() = 6
= 0
(((( = 0
(((() = 2
(((())( = 4
()(() = 2
()(()) = 6

- harishvc

---

这个程序会输出 "()(()" 的结果为 4，但正确答案应该是 2。 - Yo Hsiao

Answer 5

如果您愿意采用动态方法查找有效元素并尝试通过检查相邻元素来增加其大小，则可以在不使用传统堆栈的情况下实现O(n)。

首先，我们找到一个单一的'()'

然后，我们尝试找到包括它在内的更长字符串：

可能性如下：

• ('()')，我们检查前面和后面的索引
• '()'()，我们检查下一个有效单位，以便在搜索中不重复。

接下来，在每个循环中更新当前检查的起始和结束索引

在有效字符串的末尾，将当前计数器与迄今为止的最大长度进行比较，并在必要时进行更新。 Python代码的GitHub链接 点击此处。

- Niranjan Nareshan

Answer 6

下面的解决方案具有O(n)时间复杂度和O(1)空间复杂度。

这很直观。我们首先从左到右遍历字符串，使用通常用于检查括号有效性的“count”方法查找最长的有效括号子串。在执行此操作的同时，如果找到，则记录此类子串的最大长度。

然后，我们从右到左执行相同的操作。

算法如下：

// Initialize variables

1. count = 0, len = 0, max_len_so_far = 0


// Check for longest valid string of parens while traversing from left to right

2. iterate over input string from left to right:
   - len += 1
   - if next character is '(',
         count += 1
   - if next character is ')',
         count -= 1
   - if (count == 0 and len > max_len_so_far),
         max_len_so_far = len
   - if (count < 0),
         len = 0, count = 0


// Set count and len to zero again, but leave max_len_so_far untouched

3. count = 0, len = 0


// Now do a very similar thing while traversing from right to left
// (Though do observe the switched '(' and ')' in the code below)

4. iterate over input string from right to left:
   - len += 1
   - if next character is ')',
         count += 1
   - if next character is '(',
         count -= 1
   - if (count == 0 and len > max_len_so_far),
         max_len_so_far = len
   - if (count < 0),
         len = 0, count = 0


// max_len_so_far is now our required answer

5. Finally,
   return max_len_so_far

举个例子，考虑字符串

"((())"

假设这个字符串是从零开始索引的。

我们首先从左到右遍历。

所以，在索引0处，计数将为1，然后在索引1处为2，在索引2处为3，在索引3处为2，在索引4处为1。在这一步中，最大长度甚至不会改变，因为计数再也不会为0。

然后我们从右到左走。

在索引4处，计数为1，然后在索引3处为2，然后在索引2处为1，然后在索引1处为0。
此时，长度为4，max_len_so_far=0，因此我们设置max_len = 4。
然后，在索引0处，计数为1。

此时，我们停止并返回4，这确实是正确的答案。



正确性的证明留给读者作为一个包容性练习。

注意：该算法也可以非常简单地调整为返回括号本身的最长有效子字符串，而不仅仅是其长度。

- AppyFizz

Answer 7

    static int LongestvalidParentheses()
    {
        int cnt = 0;
        string str = "()()))()";
        char f = '(';
        char s = ')';
        var chararr = str.ToCharArray();
        for (int i = 0; i < str.Length - 1; i++)
        {
            if (chararr[i] == f)
            {
                if (chararr[i + 1] == s)
                {
                    cnt++;
                }
            }
        }
        return cnt;
    }

- Neelesh Jain

---

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心找到有关如何编写良好答案的更多信息。 - Community

Answer 8

public static void main(String[] args) {
    String s="))((())";
    String finalString="";
    for(int i=0;i<s.length();i++){

         if (s.charAt(i) == '('&& s.charAt(i+1) == ')') {
         String ss= s.substring(i, i+2);
         finalString=finalString+ss;
        // System.out.println(ss);
         }

    }
    System.out.println(finalString.length());
}

- Narasimha

---

这是一个质量较低的答案。尝试添加一些额外的细节。为什么这段代码能够工作？ - Taslim Oseni

Answer 9

刚想出解决方案，如果有任何问题，请评论。

count = 0 //stores the number of longest valid paranthesis
empty stack s
arr[]; //contains the string which has the input, something like ())(()(
while(i<sizeof(arr))
{
    if(a[i] == '(' )
    {
        if(top == ')' ) //top of a stack,
        {
            count = 0;
            push a[i] in stack;
        }
    }
    else
    {
        if(top == '(' )
        {
            count+=2;
            pop from stack;
        }
        else
        {
            push a[i] in stack;
        }
    }
}

打印计数

- Haris

Answer 10

使用动态规划来存储和重复使用已经计算过的结果。

def longest_valid_paranthesis(str):
    l = len(str)
    dp = [0]*len(str)
    for i in range(l):
        if str[i] == '(':
            dp[i] = 0
        elif str[i-1] == '(':
            dp[i] = dp[i-2] + 2
        elif str[i - dp[i-1] - 1] == '(':
            dp[i] = dp[i-1] + 2 + dp[i - (dp[i-1] + 2)]

- Farrukh Taqveem Haider