如何更好地理解“最长有效括号"?问题方案? [英] How to better understand for "longest valid parentheses" problem solution?

问题描述

问题是:

给出一个仅包含字符'('和')'的字符串，找到最长的有效(格式正确)括号子字符串的长度

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring

一些例子是:

输入:(()"，输出:2

Input: "(()", output: 2

输入:)()())"，输出4

Input: ")()())", output 4

我在下面找到了这个可行的Python解决方案:

I found this working Python solution below:

def solution(s):
    if not s or len(s) == 1:
        return 0

    stack = [-1]
    a = 0
    for i,c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            stack.pop()
            if stack:
                a = max(a, i - stack[-1])
            else:
                stack.append(i) 
    return a

我无法理解为什么该解决方案有效.我已经逐步处理了一些示例输入，但是我看不出它为什么起作用.

I'm having trouble understanding why this solution works. I've worked step-by-step on some example inputs, but I can't see why it works.

如果我理解正确，那么每次遇到左括号时，堆栈都会简单地添加索引.否则，将弹出堆栈，并采用当前索引和最后一个左括号之间的差值.

If I understand correctly, the stack is simply appending the indices every time a left parentheses is encountered. Otherwise, the stack is popped and we're taking the difference between the current index and the last left parentheses.

我的问题是，为什么先弹出堆栈然后再测量长度?为什么要从第二个括号到最后一个括号进行测量?如果堆栈为空，我也无法理解为什么我们有一个 stack.append(i):我不明白这里的逻辑.

My question is why is the stack popped first and then the length is measured? Why are we measuring from the 2nd to last parentheses? I'm also failing to understand why we have a stack.append(i) if the stack is empty: I don't understand the logic here.

推荐答案

堆栈包含不平衡字符的索引，始终按升序排列.堆栈的顶部(即 stack 列表中的最后一个值)是当前不平衡的最右边字符(或 -1 的特殊索引，它指向一个位置如果当前没有任何不平衡字符，则在字符串的开始之前".

The stack contains indexes of unbalanced characters, always in increasing order. The top of the stack (i.e. the last value in the stack list) is the rightmost character that is currently unbalanced (or a special index of -1 that refers to a position "before the beginning" of the string if there are not any unbalanced characters currently).

堆栈底部是最右边的不平衡)字符的索引，如果没有不平衡的)，则为 -1 到目前为止已经看到.堆栈中的所有其他值将始终是迄今不平衡的(字符)的索引.稍后，当我们继续遍历字符串时，我们可能会平衡它们.

At the bottom of the stack is the index of the rightmost unbalanced ) character, or -1 if there has been no unbalanced )s seen so far. All of the other values in the stack will always be indexes of so-far unbalanced ( characters. We might balance them later, as we continue to iterate over the string.

当我们在输入字符串上的迭代中遇到一个新字符时，我们可能会采取三种可能的操作.

When we come to a new character in our iteration over the input string, there are three possible actions we might take.

1. 如果新字符是(，我们知道它是不平衡的(目前为止，因为它是我们处理的最后一个字符)，所以我们总是将其推入堆栈的顶部./li>

1. If the new character is a (, we know it is unbalanced (for now, since it's the last character we've processed), so we always push it onto top of the stack.

在其他两种情况下，新字符为).对于这两种情况，我们都希望从堆栈顶部弹出一个值，因为以前的值不再是最右边的不平衡字符.

In the other two cases, the new character is ). For both, we want to pop a value off the top of the stack, since the former value is no longer the rightmost unbalanced character.

1. 如果在我们弹出值后堆栈不为空，则弹出的索引表示不平衡的(字符，而当前的)刚刚使它平衡

1. If the stack is not empty after we pop a value, then the popped index represented an unbalanced ( character, and the current ) has just balanced it.

在这种情况下，我们当前的字符是平衡子字符串的一部分，因此我们检查它是否是迄今为止我们所见过的最长的子字符串.堆栈中的最后一个值是最右边的不平衡字符的索引，而我们的平衡子字符串就从其右边开始.因此，当前子字符串的长度为 i-stack [-1] ，并且 max 调用将替换 a (最长的长度子串)，如果它大于 a 的旧值，则使用新的长度.

In this case, our current character is part of a balanced substring, so we check if it's the longest such substring we've seen so far. The last value in the stack is the index of the rightmost unbalanced character, and our balanced substring begins just to its right. The length of the current substring is thus i - stack[-1], and the max call will replace a (the length of the longest substring seen previously) with this new length if it's larger than a's old value.

如果在我们弹出一个值后堆栈为空，那么我们弹出的值就是堆栈的底部.正如我上面提到的，底部值是不平衡的)字符(或 -1 代表字符串开头)的索引.如果我们弹出它，则意味着我们当前的)不平衡！在这种情况下，我们用自己的索引替换弹出的值.这是堆栈的新底部，是最右边最不平衡的)的索引.

If the stack is empty after we popped a value, then the value we popped was the bottom of the stack. As I mentioned above, the bottom value is an index of an unbalanced ) character (or -1 representing the start of the string). If we've popped it, that means our current ) is unbalanced! In this case, we replace the popped value with our own index. This is the new bottom of the stack, the index of the a new rightmost unbalanced ).

这篇关于如何更好地理解“最长有效括号"?问题方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！