32. The longest valid bracket

LeetCode leetcode-cn.com/problems/lo…

The title

Given a string containing only ‘(‘ and ‘)’, find the length of the longest substring containing valid parentheses.

Example 1:

Input:"()"Description: The longest valid parenthesis substring is"()"
Copy the code

Example 2:

Input:") () ())"Description: The longest valid parenthesis substring is"() ()"
Copy the code

Their thinking

Thinking: the stack

In this case, to find valid parentheses, you might need to expand from the inside out, which is the nature of the stack.

Let’s try to solve this problem by using a violent solution.

Valid parentheses come in pairs, so we try to list all possible non-empty even length substrings to see if they are valid.

When we encounter an open parenthesis (, we push it onto the stack. When a close parenthesis is encountered, an open parenthesis is popped from the stack (, the substring is invalid if there are no open parentheses left in the stack or if there are elements left in the stack after traversal is complete. Loop through, updating the maximum length. The specific code is as follows:

def longestValidParentheses(self, s: str) -> int:
    def is_valid(s):
        stack = []
        for i in range(len(s)):
            if s[i] == '(':
                stack.append('(')
            elif stack and stack[- 1] = ='(':
                stack.pop()
            else:
                return False
        return not stack

    max_len = 0
    for i in range(len(s)):
        for j in range(i+2, len(s)+1.2) :if is_valid(s[i:j]):
                max_len = max(max_len, j-i)

    return max_len
Copy the code

But the result is a timeout. Because our method is to list all possible non-empty even substrings from the string, the time required here is O(n^2).

Here, we try to optimize.

The brute force solution above is to list all possible substrings first. In this case, we directly determine the validity of the traversal substring while maintaining the maximum length.

One caveat here is that you need to start by pushing -1 on the stack (explained later). The specific implementation method is as follows:

  • When faced with(, push its index onto the stack;
  • When faced with)Pops the top element of the stack, calculates the effective length, loops through, and maintains the maximum length.

In step 2, calculate the effective length. Here we simply subtract the index of the element at the top of the stack from the character index currently traversed. The index at the top of the stack corresponds to the index of the first character of the valid substring, as illustrated in Example 1:

"()"
Copy the code

According to the previous method, the implementation process is as follows (stack is the stack, I is the traversal index value) :

  • First the- 1Push it onto the stack, sostack = [-1].
  • Let’s start traversing, first encountered(, the index is pushed onto the stack,Stack = [-1, 0], I = 0;
  • Keep going, or(, index push,stack=[-1, 0, 1], i = 1;
  • And finally, what happens is), push the top element off the stack,stack=[-1, 0], i = 2At this point, the maximum effective length is calculated: the current character index minus the index of the top element on the stack, i.elen = 2-0. And then this top element, 0, is the one we started with(The index corresponding to the first open parenthesis.

As for why -1 is pushed on the stack first, here’s an example:

"()"
Copy the code

If such a string is encountered, the stack is empty when the traversal is complete, as described above. Then calculating the maximum effective length would be wrong. If -1 had been pushed on the stack, the element in the stack would have been stack=[-1], and this would have computed the result.

Here’s another example:

"()"
Copy the code

In this string, if () is encountered first, then the stack operation needs to be performed first. If there are no elements in the stack, the same error will be reported.

The specific implementation code is as follows.

Code implementation

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        max_len = 0
        stack = []
        # if ') 'is encountered, the element should be ejected first
        # when the '()' character is encountered, -1 comes into play when calculating the length
        stack.append(- 1)
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[- 1])
        return max_len
Copy the code

Achieve results

conclusion

  • In order to find valid parentheses, it is possible to run the parentheses from the inside out, which is similar to the stack first in last out feature, you can consider using the stack method to solve the problem.
  • First try to solve the problem using the method of violent solution. Here, list all the non-empty even substrings, check their validity, count the maximum valid length (but find timeout after execution).
  • The violence solution is optimized instead of using the enumeration method. When traversing a string directly, check whether the traversed substring is valid and calculate the valid length as follows:
    • First the- 1Push into the stack (specific reasons have been analyzed previously)
    • When faced with(, push its index onto the stack,
    • When faced with), and calculate the effective length (subtract the top element of the stack from the character index currently traversed).
    • Loop through to get the maximum effective length.

The article is original, if you think it can be written, welcome to focus on praise. The wechat public account “Shusuoji Lu” is updated synchronously, also welcome attention to like.