Topic:

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

The sample

  • 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

The topic

Violent solution

Timeout (217/230 pass test cases)

  • Sets the start and end Pointers to split the string
  • Double – layer loop, meet the requirements of the character will appear in the interception process
    • The odd length must not meet the requirements, do not check whether the conformity
    • If the length is smaller than an existing character that meets the requirements, the compliance check is not performed
  • Check whether the string meets the requirements
    • If one element is ‘(‘ the next element is ‘)’, remove the two characters and loop again
    • Strings that meet the requirements are removed from the verification. If there are any remaining elements, they are invalid
/** * @param {string} s * @return {number} */
var longestValidParentheses = function(s) {
  let len = s.length;
  let start = 0;
  let end = len;
  let _result = 0;
  while (start < len) {
      while (end > start) {
          if ((end - start + 1) % 2 && (end - start) > _result) {
              let str = s.slice(start, end)
              if(! match_str(str)) { _result =Math.max(_result, end - start);
              }
          }
          end--
      }
      start++
      end = len;
  }
  return _result
  function match_str(str) {
      let i = 0;
      while (i < str.length - 1) {
          if (str[i] === '(' && str[i + 1= = =') ') {
              str = str.replace('()'.' ');
              i = 0
          } else {
              i++
          }
      }
      return str.length
  }
};
Copy the code

The official answer

Dynamic programming

  • The record traversal string records the required character length at the end of each element
  • None of the valid characters will end in ‘(‘, the default count is 0, and ‘(‘ will not be processed when recorded
  • Skip the ‘(‘, and add up, and you should get even numbers
( ) ( ( ) ) . X X
dp[0] dp[1] dp[2] dp[3] dp[4] dp[5] . dp[i-1] dp[i]
0 2 0 0 2 dp[5] . dp[i-1] dp[i]

A dp [5] :

  1. 0 if dp[5] is ‘(‘
  2. If dp[5] is ‘)’:
  • It is preceded by a ‘(‘ to match it
  • There is no ‘(‘ in front of it to determine whether there is a match:
  • The character length of the last platoon was: dp[4]
  • Current pointer position: 5

matching

The sum of the length of the previous set of matching characters and the length of this match:


That is:


If 5 becomes I then: if, then:


Don’t match

The string that the pointer gets at that position does not satisfy the condition

  • If I is 2 and dp[0] is ‘(‘), if I is 2 and dp[0] is ‘(‘),
  • Dp [0] does not have a queue length, but it can queue with dp[1]. If s[i-1] is ‘(‘, the queue length should be:

Take a string and specify the position character using either ‘[]’ or chartAt

Boundary processing:

  • When I is 1,dp[i-2] does not exist. The default value is 0
  • If i-dp[i-1]-2 is less than 0, dp[i-dp[i-1]-2 does not exist. The default value is 0
/** * @param {string} s * @return {number} */
var longestValidParentheses = function(s) {
   let len = s.length,
       _result = 0;
   if (len === 0) return _result
   let dp = Array(len).fill(0);
   for (let i = 1; i < s.length; i++) {
       if (s.charAt(i) == ') ') {
           if (s.charAt(i - 1) = ='(') {
               dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
           } 
           else if (
             i - dp[i - 1] > 0 && 
             s.charAt(i - dp[i - 1] - 1) = ='('
            ) {
              dp[i] = dp[i - 1] + 
                      ((i - dp[i - 1> =])2 ? dp[i - dp[i - 1] - 2] : 0)
                      + 2;
           }
           _result = Math.max(_result, dp[i]); }}return _result
};
Copy the code

The stack

  • Like the brute force method, the index computes the length of the string in accordance with the rules
  • The difference is that there is no need to loop through character interceptions
  • From front to back, if the rule is interrupted, pick up where it left off
  • Finally returns the longest character length

Rules are broken

  • ‘(‘ can be followed by ‘(‘ one by one, only if the number of ‘)’ is less than ‘(‘
  • Create a new array (stack) to store indexes of elements that might have matching characters (used to calculate length)

cycle

  • When ‘(‘ is encountered, which is the starting mark, save

  • If ‘)’ is encountered, find the nearest ‘(‘ matches it (removes the last element index from the array to be matched).

    • If there are no elements in the array to be matched, the previous characters have been matched. If there are any matches, the position of the pointer is the starting point
    • If there are no matched elements in the array, there is a character that has not been matched. In this case, the length of the string matching from the last starting point to the pointer position is increased by one: the last element in the array to be matched is the starting point, and the pointer is the end point

    The matching character starts at index 0, and if it starts at -1, the array to be matched contains -1 by default

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

Forward and reverse combination

  • ‘(‘ and ‘)’ are the starting points

Start from left to right:

  • ‘(‘ quantity greater than ‘)’ continues to be searched, and any additional ‘(‘ may be completed later
  • ‘)’ less than ‘(‘ the count stops, the count returns to zero, and the match is interrupted
  • ‘(‘ quantity equals ‘)’ is found to satisfy the requirement,
  • The count of ‘(‘ may end with a recirculation greater than ‘)’, i.e. : left>right, the record length is 2*right, a set of ‘()’

And from right to left:

  • ‘(‘ quantity less than ‘)’ continues to be searched, and any additional ‘)’ that may later be completed
  • If the count is greater than ‘(‘ the count stops, the count goes to zero, and the match is interrupted
  • ‘(‘ quantity equals ‘)’ is found to meet the required record length
  • The count of ‘)’ may end in a loop greater than ‘(‘, i.e., right>left, and the record length is 2*left, a set of ‘()’

Returns the maximum value of a record

/** * @param {string} s * @return {number} */
var longestValidParentheses = function(s) {
  let left = 0, 
  right = 0, 
  maxlength = 0;
  for (let i = 0; i < s.length; i++) {
      if (s.charAt(i) == '(') {
          left++;
      } else {
          right++;
      }
      if (left == right) {
          maxlength = Math.max(maxlength, 2 * right);
      } else if (right > left) {
          left = right = 0;
      }
  }
  left = right = 0;
  for (let i = s.length - 1; i >= 0; i--) {
      if (s.charAt(i) == '(') {
          left++;
      } else {
          right++;
      }
      if (left == right) {
          maxlength = Math.max(maxlength, 2 * left);
      } else if (left > right) {
          left = right = 0; }}return maxlength;
};
Copy the code