Force deduction 32 questions longest valid bracket

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 .

I/o sample

 Input ：s = "(()"
 Output ：2
 explain ： The longest valid bracket substring is  "()"

 Input ：s = ")()())"
 Output ：4
 explain ： The longest valid bracket substring is  "()()"

 Input ：s = ""
 Output ：0

Solution a violent solution

1. First, build a function that verifies whether it is a valid function
2. Next, you can intercept the string for judgment , Intercept from large to small
3. There are two ways , One is two for Loop head and tail traversal , One is based on the string 2 The properties of multiples of are reduced gradually

 int longestValidParenthese(string s)
  {
    
    int maxlength=0;
    int length=s.size();

    if(length<=1)
    {
    
        return maxlength;
    }
    
    // double for Loop through 
    // for(int i=0;i<length;i++)
    // {
    
    // for(int j=length-1;j>=i;j--)
    // {
    
    // int lengthStr=j-i+1;
    // string str=s.substr(i,lengthStr);
    // if(isVaild(str))
    // {
    
    // maxlength=(lengthStr>maxlength)?lengthStr:maxlength;
    // }
    // }
    // } 


    // Increase in logarithm 

    int moveLength=(length/2)*2;

    int i=0;
    string str;
    for(i=0;moveLength>0;i++)
    {
    
        str=s.substr(i,moveLength);


        if(isVaild(str))
        {
    
            maxlength=moveLength;
            break;
        }

        if(i+moveLength>=length)
        {
    
            moveLength=moveLength-2;
            i=-1;
        }
    }
     return maxlength;
  } 

  bool isVaild(string s)
  {
    
      stack<char>sta;
      map<char,char>array={
    {
    ')','('}};

      for(auto i:s)
      {
    
          if(array.count(i))
          {
    
              if(sta.empty()||sta.top()!=array[i])
              {
    
                  return false;
              }
              sta.pop();
          }
          else{
    
              sta.push(i);
          }
      }
      if(sta.empty())
      {
    
          return true;
      }
      else{
    
          return false;
      }
  }

Solution 2 uses the dynamic programming method

    int longestValidParentheses2(string s)
    {
    
        int maxlength=0;
        int length=s.size();

        //  establish dp Array 

        vector<int>dp(length,0);

        for(int i=1;i<length;i++)
        {
    
            // It is calculated according to whether the value is a right parenthesis 
            // If it is ） Update dp Array , Otherwise, do not update 

            if(s[i]==')')
            {
    
                // If the ） Corresponding （ Coordinates of exist 
                // And the value is exactly equal to （
                if(s[i-1]=='(')
                {
    
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                }
                else if((i-dp[i-1]-1)>=0&&(s[i-dp[i-1]-1])=='(')
                {
    
                    dp[i]=dp[i-1]+((i-dp[i-1]-2)>=0?(dp[i-dp[i-1]-2]):0)+2;
                }
                maxlength=max(maxlength,dp[i]);
            }
        }
        return maxlength; 
    }

Solution 3 uses stack method

    // The method of using stack 
     int longestValidParentheses3(string s)
     {
    
         int maxlength=0;
         // The stack stores the coordinates 
         stack<int>stk;

         // First of all -1 Initialization stack 
         // Represents the position of the first value 
         stk.push(-1);
         
        for(int i=0;i<s.size();i++)
        {
    
            if(s[i]=='(')
            {
    
                stk.push(i);
            }
            // When s[i]=')', Execute out of stack 
            // And according to whether the stack is empty , Execute maximum length  
            else{
    
                stk.pop();

                // If the current stack is empty , Then put the current coordinates on the stack 
                if(stk.empty())
                {
    
                    stk.push(i);
                }
                else{
    
                    maxlength=max(maxlength,i-stk.top());
                }
            }
        }
        return maxlength;
     }

Solution 4: counting by brackets

    int longestValidParentheses4(string s)
    {
    
        // Define the number of left and right parentheses 
        int left=0,right=0;
        int maxlength=0;
        int length=s.size();

        for(int i=0;i<length;i++)
        {
    
            if(s[i]=='(')
            {
    
                left++;
            }
            else{
    
                right++;
            }
            if(left==right)
            {
    
                maxlength=max(maxlength,2*right);
            }
            // When the number of right parentheses is greater than the number of left parentheses, the left and right parentheses count is reset 
            else if(right>left)
            {
    
                left=right=0;
            }
        }


        // Traversal in reverse order 
        // Initializes the count value of the left and right parentheses 0

        left=right=0;

        for(int i=length-1;i>=0;i--)
        {
    
            if(s[i]=='(')
            {
    
                left++;
            }
            else{
    
                right++;
            }
            if(left==right)
            {
    
                maxlength=max(maxlength,2*left);
            }
            // When the number of left parentheses is greater than the number of right parentheses, the left and right parentheses count is reset 
            else if(left>right)
            {
    
                left=right=0;
            }

        }
    return maxlength;
    }