Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

Leetcode-cn.com/problems/lo…

Given a string containing only ‘(‘ and ‘)’, find the length of the longest valid (well-formed and continuous) parenthesis substring.

Example 1:

Input: s = “(()” Output: 2 Explanation: The longest valid parenthesis substring is “()”

Example 2:

Input: s = “)()())” Output: 4 Explanation: The longest valid parenthesis substring is “()()”

Example 3:

Input: s = “output: 0

 

Tip:

  • 0 <= s.length <= 3 * 104
  • s[i] 为 '(' 或 ') '

Idea 1: stack + violence

  • Time complexity: O(n^2)
  • Space complexity: O(n)
  • A similar topic
  • 20. Valid brackets
  • A. valid b. valid C. valid D. valid
    • Valid, generated in even length string
    • Is it a stack solution? Exactly the same as problem 20
      • The length can be obtained by differentiating the index before and after the valid substring
  • Timeout due to enumeration of violence
/ * * *@param {string} s
 * @return {number}* /
var longestValidParentheses = function(s) {
    var max = 0;
    function isValid(str){
        var stack = [];
        for(var i = 0; i < str.length; i++){if(str[i] == '('){
                stack.push('(');
            }else{
                if(stack.length == 0) {return false;
                }
                var topEle = stack.pop();
                if(topEle ! ='(') {return false; }}}return stack.length == 0;
    }
    for(var i = 0; i < s.length; i++){for(var j = i + 2; j <= s.length; j+=2) {if(isValid(s.slice(i,j))){
                max = Math.max(max,j-i); }}}return max;
};You can also set a sentry for the stack, otherwise you don't need to check whether the stack is empty every time/ * * *@param {string} s
    * @return {number}* /
    var longestValidParentheses = function(s) {
    var max = 0;
    function isValid(str){
        var stack = [The '#'];
        for(var i = 0; i < str.length; i++){if(str[i] == '('){
                stack.push('(');
            }else{
                var topEle = stack.pop();
                if(topEle ! ='(') {return false; }}}return stack.length == 1;
    }
    for(var i = 0; i < s.length; i++){for(var j = i + 2; j <= s.length; j+=2) {if(isValid(s.slice(i,j))){
                max = Math.max(max,j-i); }}}return max;
    };
Copy the code

Idea 2: stack + optimal solution + sentry

  • Time complexity: O(n)
  • Space complexity: O(n)
  • Train of thought
  • Stack and take the optimal solution
    • Refer to solution 1
      • Instead of going through all the combinations of substrings and finding the optimal solution
      • It is better to judge the validity of the first I characters and get the optimal solution in the traversal process
  • The sentry
    • When the first element is a close parenthesis, there is no element on the stack, violating the rule that the open parenthesis should be pushed on the stack
    • When the stack is empty, close parentheses are pushed onto the stack and continue traversal as a sentinel node
  • The illustration

/ * * *@param {string} s
 * @return {number}* /
var longestValidParentheses = function(s) {
    var max = 0;
    var stack = [-1];
    for(var i = 0; i < s.length; i++){if(s[i] == '('){
            stack.push(i);
        }else{
            stack.pop();
            if(stack.length == 0){
                stack.push(i);
            }else{
                max = Math.max(max,i - stack[stack.length-1]); }}}return max;
};
Copy the code

Idea 3: on both sides of the force + intuitive method

  • Time complexity: O(n)
  • Space complexity: O(1)
  • A valid parenthesis string is ‘()’, ‘(())’, ‘()()’, and ‘()()’
  • The reverse: ‘(()’, ‘())’, ‘(‘, ‘)’ is invalid as a whole
  • Set the left and right variables
    • Traverse from left to right
      • Encountered ‘(‘, left++
      • Encountered ‘)’, right++
      • When left == right, it belongs to the valid parenthesis group
      • When right > left, it belongs to the invalid parenthesis group
        • Such as’ () ‘
        • Initialize left = right = 0 and continue to traverse to the right
    • After the loop, reset left = right = 0
    • And I’m going to do the same thing from right to left
/ * * *@param {string} s
 * @return {number}* /
var longestValidParentheses = function(s) {
    var max = 0;
    var left = 0;
    var right = 0;
    for(var i = 0; i < s.length; i++){if(s[i] == '('){
            left++;
        }else{
            right++;
        }
        if( left == right){
            max = Math.max(max,2 * left);
        }else if(right > left){
            left = right = 0;
        }
    }
    left = right = 0;
    for(var i = s.length-1; i >=0; i--){if(s[i] == '('){
            left++;
        }else{
            right++;
        }
        if(left == right){
            max = Math.max(max,right * 2);
        }else if(left > right){
            left = right = 0; }}return max;
};
Copy the code

Idea 4: Dynamic planning

  • Time complexity: O(n)
  • Space complexity: O(n)
  • The illustration
  • 3. What is the meaning of this passage
  • A valid string must end with “)”
  • Here we have the state transition arraydp[i]
    • Represents the length of the longest valid substring ending with a character at subscript I
  • A valid string ending with a “)” character is one of the following
    • 1、”(“+”)“< = >…()
      • Equivalent to: s[I] == ‘)’ &&s [I -1] == ‘(‘
      • So the last two characters must be part of the longest valid substring of length 2
      • The recursive formula is:
        • dp[i] = dp[i-2] + 2
    • 2、”)“+”)“< = >…). )
      • 2.1、”)“+”)“+”)“< = >…). ))
        • Equivalent to: s[I] == ‘)’ &&s [I -1] == ‘)’ &&s [I -2] == ‘)’
        • The recursive formula is:
        • dp[i] = dp[i-1] + 0
      • 2.2、”(“+”)“+”)“< = >. ())
        • Equivalent to: s[I] == ‘)’ &&s [I -1] == ‘)’ &&s [I -2] == ‘(‘
        • Where: s[i-2] == ‘(‘)
          • Note S [i-2] and s[i-1] can form a pair of valid parentheses
          • Equivalent to the last part of the length of the longest valid substring dp[i-1] “()” ending in i-1
          • [i-dp[i-1]-1] == ‘(‘)
        • The other way around is when the position leading to the current legal sequence happens to be an open parenthesis
        • If dp[i-dp[i-1]-1] == ‘(‘
          • dp[i-dp[i-1] – 2] + 2
          • This means that the last parenthesis “)” is paired with the position before the previous legal sequence “(” form a pair, plus 2
          • As shown in figure: 2+2 = 4
        • The recursive formula is:
          • dp[i] = dp[i-1] + dp[i-dp[i-1]-2]+2
/ * * *@param {string} s
 * @return {number}* /
var longestValidParentheses = function(s) {
    var max = 0;
    var n = s.length;
    var dp = new Array(n).fill(0);
    for(var i = 1; i < n; i++){if(s[i] == ') ') {// The close parenthesis is preceded by the open parenthesis
           if(s[i-1] = ='('){
               dp[i] = ( i >= 2 ? dp[i-2] : 0) + 2;
           }
           // If the current close parenthesis is preceded by a close parenthesis and the previous legal subsequence is preceded by an open parenthesis and the current close parenthesis, the maximum number of sequences is increased by 2
           else if(i - dp[i-1] > 0 && s[i - dp[i-1] - 1] = ='('){
               dp[i] = dp[i-1] + ( (i - dp[i-1] > =2)? dp[i - dp[i-1] - 2] : 0 ) + 2;
           }
            max = Math.max(max,dp[i]); }}return max;
};
Copy the code