leetcode 32. Longest valid bracket

Title Description

Give you one that only contains ‘(’ and ‘)’ String , Find the longest effective （ The format is correct and continuous ） The length of the bracket substring .
Example 1：
Input ：s = “(()”
Output ：2
explain ： The longest valid bracket substring is “()”
Example 2：
Input ：s = “)()())”
Output ：4
explain ： The longest valid bracket substring is “()()”
Example 3：
Input ：s = “”
Output ：0
Tips ：
0 <= s.length <= 3 * 10⁴
s[i] by ‘(’ or ‘)’

analysis

Together hard Difficult bracket matching problem , A sequence of parentheses containing only one kind of parentheses is legal , If and only if the number of left parentheses equals the number of right parentheses , And the number of left parentheses in any prefix is not less than the number of right parentheses . We use a count variable , When you meet the left parenthesis ++, Right parenthesis –, It is easy to determine whether a sequence that begins with a certain subscript is legal , But this question needs to find the length of the longest legal bracket sequence .

A legal sequence of parentheses can be subdivided into several categories ：

• side-by-side ：(A) + (B), That is, several legal parenthesis sequences are connected .
• Inclusive ：((A)(B)), A few legal parentheses are added to the sequence .

Do not use stack emulation

Use an example to simulate the process of matching the lower brackets ：
（）（（））（））（（（）)

Traverse the first left parenthesis ,cnt++, the second cnt–, here cnt by 0, Indicates that the parentheses traversed from the beginning to the current are a legal sequence of parentheses , But there is no guarantee that it is the longest legal sequence starting with the first left parenthesis , Because there may be parallel legal sequences .

Continue to traverse and find that the following four characters can also form a legal sequence , Traverse to the 6 In characters ,cnt Back again 0 , At this time, the longest legal bracket sequence that can be extended from the opening left bracket is to the th 6 Characters .

Continue to traverse the following 1 A left bracket ,cnt = 1, Right parentheses are encountered after ,cnt = 0, At this point, the length of the longest bracket sequence is extended to 8, But then came a closing parenthesis , bring cnt = -1, There is no matching left bracket before the right bracket , Adding this right parenthesis sequence is illegal , Therefore, the preceding legal sequence of parentheses cannot be extended , Even if there is a juxtaposed sequence of legal parentheses, it has nothing to do with the preceding sequence of parentheses , So there are negative numbers cnt It is equivalent to a separate signal .

Continue to traverse to the last set of parentheses in the example , It consists of three left parentheses and two right parentheses , At the end of traversal cnt = 1, Because only in cnt = 0 Update the length of the longest bracket sequence , So the length of the legal sequence in the last sequence is not statistically .

Through the simulation of this example, we can find , Use count variables to simulate , meet cnt Zeroing updates the length of the longest sequence , meet cnt A negative number will clear the length of the previously accumulated legal sequence . If we do not consider the last sequence in which the number of left parentheses is greater than the number of right parentheses , The length of the longest legal sequence is the length of the longest legal sequence in the previous section .

Let's look at the last bracket sequence , The resultant subsequence is the last four characters (()), When traversing to the penultimate character cnt = 2, It's not a special number , So we can't determine the left endpoint of the longest legal bracket sequence in this sequence , Or only by traversing backwards from the right can we find out where the left endpoint is .

For the special case of the last bracket sequence , There are two ways to do this . After traversing the sequence of parentheses , Then traverse backwards , Meet the right bracket cnt++, Left parenthesis cnt–, Also meet cnt = 0 Update the longest sequence length , meet cnt < 0 Clear the accumulated longest sequence length ; Another way is to simulate the sequence of lower brackets , Then flip the parenthesis sequence and swap the left and right parentheses , And then traverse the lower bracket sequence , The effect is the same as the first method , The advantage is that you can reuse the code you are traversing .

The code without stack emulation is as follows ：

class Solution {
    
public:
    int count(string &s){
    
        int len = 0,cnt = 0,ans = 0;
        for(int i = 0;i < s.size();i++){
    
            if(s[i] == '(') cnt++;
            else    cnt--;
            len++;
            if(!cnt)    ans = max(ans,len);
            else if(cnt < 0)    cnt = len = 0;
        }
        return ans;
    }
    int longestValidParentheses(string s) {
    
        int ans = count(s);
        reverse(s.begin(),s.end());
        for(int i = 0;i < s.size();i++){
    
            if(s[i] == '(') s[i] = ')';
            else    s[i] = '(';
        }
        ans = max(ans,count(s));
        return ans;
    }
};

Stack simulation

Without using the stack simulation, we know only cnt and len, Need to be in cnt < 0 To update the starting point of the longest legal sequence . For the general bracket matching problem , The way to use stack emulation is to put it on the stack when you encounter the left parenthesis , The right bracket comes out of the stack , If the stack is not empty during the traversal and the stack is empty after the traversal, it means that the bracket sequence is legal . The disadvantage of stack emulation is that it requires extra space , The advantage is that each time the left parenthesis comes out of the stack, it meets the matching right parenthesis , This makes it easy for us to count the length of the bracket sequence . Recall the reason why you need to traverse twice without using the stack for simulation , Because of the last part of the bracket sequence, we may not be able to determine the position of the left bracket paired with the rightmost right bracket , There is no such concern when using stack emulation . For each right parenthesis in a legal sequence of parentheses , We must be able to find the matching left parenthesis ; Could not find the matching left parenthesis , Then the right parenthesis must not be a member of the legal parenthesis sequence .

Let's use the stack to simulate the above example （ You can simulate this process on paper , Easy to understand ）
（）（（））（））（（（）)

Let's start with a sentinel node -1 Push , Why use sentry nodes , I'll explain later .

Traverse the first left parenthesis , Subscript it to the stack , Because all the left parentheses are put on the stack , So there is no need to save characters , Save the subscript so that we can count the length of the sequence . Traverse the closing bracket of the second character , When you meet the right parenthesis, you can get out of the stack , At this point, the length of the legal bracket sequence should be 2, And the current right parenthesis subscript 1 Subtract the current stack top element -1 It happens to be 2.

Traverse the sequence of parentheses in the second part , Two left parentheses are put on the stack , Traverse to the right bracket of the fifth character , Stack top element out of stack , At this point, the subscript of the traversal to the right bracket is 4, The subscript of the new stack top element is 2, That is, the position of the last left parenthesis paired with the current right parenthesis ,4 - 2 = 2, That is, the length of the longest legal bracket sequence ending with the current closing bracket . Continue to traverse the next closing bracket , The left bracket at the top of the stack comes out of the stack , At this point, there is still the sentinel node that first enters the stack -1, The subscript of the current closing bracket 5, subtract -1 be equal to 6, That is, the length of the longest legal bracket sequence ending with the current closing bracket .

Traverse the third part of the bracket sequence , The traversal process of the first two characters is the same as above , Left bracket in stack , When closing the parenthesis, the element at the top of the stack is out of the stack , Update the length of the longest legal bracket sequence ending with the current element . When traversing to the next closing bracket , There are only sentinel nodes in the stack -1 了 , It will not match the right parenthesis after the stack , There is no need to update the solution , But you need to stack the current closing bracket as a new sentinel node , The sentinel node here indicates the previous position of the left endpoint of the new legal bracket sequence , So you need to start with -1 The team . If there is a closing parenthesis after it , Just keep going out and in , This keeps the sentinel node always in the following right parenthesis .

Traverse the fourth part of the bracket sequence , Three left parentheses are put on the stack , Then two right parentheses appear on the stack , Update solution . At this time, you can notice , When traversing to the last closing bracket , The top element of the stack is the matching left parenthesis , It needs to be released in time , The new stack top element is the subscript of the last character of the matching left bracket , The solution can be updated by subtracting two character subscripts .

The correctness of the stack simulation algorithm lies in , When we traverse the sequence of parentheses, we must traverse each right parenthesis , The top element of the stack is the matching left parenthesis , If the new top stack element is a left bracket after the top stack element is out of the stack, it means that the left bracket has not met the matching right bracket , The sequence of legal parentheses ending with the right parenthesis currently traversed can only extend to the left to the position of the matched left parenthesis ; If the new top element is a sentinel node （ The only element left in the stack is the sentry ）, This indicates that the sequence of parentheses before the right parenthesis and the left parenthesis that it matches are already matched , The position of the sentinel node is the last position of the starting point of the legal bracket sequence , Then we can find the length of the complete legal bracket sequence .

This problem code is often uncomplicated , One of the difficulties is the need to consider all the circumstances , For example, the examples used need to contain parallel brackets , Illegal bracket sequence and the case that the number of left brackets in the last bracket sequence is greater than the number of right brackets ; Another difficulty is to find the matching left bracket for the right bracket , Judge according to the situation in the stack , See if the paired bracket sequence can be extended to the left , And skillfully use the sentinel node to record the previous position of the beginning position of the new legal bracket sequence .

The code using stack emulation is as follows ：

class Solution {
    
public:
    int longestValidParentheses(string s) {
    
        vector<int> stk;
        stk.push_back(-1);
        int res = 0;
        for(int i = 0;i < s.size();i++){
    
            if(s[i] == '(') stk.push_back(i);
            else{
    
                stk.pop_back();
                if(!stk.size()) stk.push_back(i);
                else    res = max(res,i - stk.back());
            }
        }
        return res;
    }
};