This is the 15th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The longest parenthesis substring

Problem description

Given a string of length N containing only the characters ‘(‘ and ‘)’, calculate the length of the longest well-formed parenthesis substring.

Example:

Input: “(())”

Output: 4

For “(())”, the longest properly formed substring is “(())”, so 4.

To analyze problems

For bracket matching problem, the most intuitive idea is to use the stack to solve. So, we can also use the stack to solve this problem. Specifically, as we iterate over a given string, we always need to ensure that the bottom element of the stack is the index of the last unmatched closing bracket of the currently iterated element, and that the other elements in the stack maintain the index of the left bracket.

  1. If we encounter an open parenthesis’ (‘, we put its subscript on the stack;
  2. If a close parenthesis’) ‘is encountered, there are two cases;
    • If the stack is empty, the current close bracket is an unmatched close bracket,
    • If the stack is not empty at this point, the subscript of the close parenthesis minus the top element of the stack is “the length of the longest valid parenthesis ending in that close parenthesis”, which is then used to update the maximum value.

Need to pay attention to some here, because at first the stack is empty, if the first character of a left parenthesis, we will put the corresponding indices in the stack, so that it can not meet the needs of the bottom of the stack will always save is the last one is not matching the right parenthesis subscript this condition, in order to ensure that the condition was established, in the beginning we need – 1 into a element in the stack.

Let’s take “())(())” as an example to see the execution process.

Let’s take a look at the code implementation.

class Solution(object): def longestValidParentheses(self, s): Stack =[] n=len(s).appEnd (-1) maxLen =0 for I in range(0,n): Pop () if not stack: stack.append(I) else: # Pop () if not stack: stack.append(I) else: maxlen = max(maxlen, i - stack[-1]) return maxlenCopy the code

The time complexity and space complexity of this algorithm are O(n).

Dynamic programming solution

In order to find the optimal solution, we generally need to consider the solution of dynamic programming. Obviously, finding the longest parenthesis substring is the optimal solution problem, so we can also use the idea of dynamic programming to solve it.

First we define dp[I] to represent the length of the longest valid parenthesis ending with the subscript I character, starting with the array dp all zeros. For a valid parenthesis substring, it obviously ends with the character ‘) ‘, so we know that the dp value of the substring ending with ‘(‘ must be 0, so we just need to solve for the value of the character’) ‘in the dp array.

We iterate through the string S from front to back.

  1. If s[I]= ‘) ‘and s[i-1]=’ (‘, the string is…. (a)… ()…” Then we can get the state transition equation as dp[I] = DP [I -2] + 2.

  2. If s[I]= ‘) ‘and s[i-1]=’) ‘, the string is………) )…” If s[i-dp[i-1]-1] = ‘(‘, then

    dp[i] = dp[i-1] + 2 + dp[i – dp[i-1] – 2]

    Explanation: If s[i-1] corresponds to ‘) ‘which is part of a valid substring, let’s say sub1, then its length is dp[i-1]. If s[I] corresponds to’) ‘which is part of a larger string, then there must be a corresponding’ (‘ that matches the substring and precedes sub1. Dp [I]=dp[i-1] + 2 + dp[i-dp[i-1] -2], where dp[i-dp[i-1] -2] represents the length of the valid substring before the string “(sub1)”, We have to add.

Let’s look at the implementation of the code.

class Solution(object): def longestValidParentheses(self, s): maxlen=0 n=len(s) dp=[0] * n for i in range(1,n): # if [I] = = ') 's and s/I - 1 = =' (', then the dp [I] = dp/I - 2 + 2 if s [I] = = ') ': if s [I - 1] = =' (' : dp[i] = 2 + (dp[i-2] if i>=2 else 0) elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1]=='(': dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i-dp[i-1]>=2 else 0) maxlen=max(maxlen,dp[i]) return maxlenCopy the code

The time complexity of this algorithm is O(n), and the space complexity is also O(n).

​