[Golang-leetcode] The longest valid parenthesis

This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Longest valid parenthesis

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

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

It’s a very short problem, and it makes sense, to find the length of the longest valid parenthesis.

The problem of matching parentheses, which I have encountered once or twice before, was solved by matching parentheses on the stack, which is a valid parenthesis if the left and right parentheses match exactly in order.

In this case, we need to find the longest valid parenthesis, which can occur anywhere. Of course, we could iterate through all of the strings, and do the same thing we did before, to see if the substring is valid, to find the longest valid parenthesis substring, but the time would be too long to not run out.

Because of the parenthesis matching problem, we can still use the stack to verify that the valid parenthesis is valid, but we need to clear the stack in time so that subsequentsubstrings can also be added to the judgment.

In addition to determining the validity of the substring, we also need to determine the length of the substring, which is easy to understand here. We use an array of labels equal to the length of the string (the default value is all zeros) for storage. After we remove a pair of parentheses from the stack, we set the labels corresponding to the two parentheses to 1.

For example, here is the picture:

Initialize the stack and tag array and iterate over the string

1. When the stack is empty and the next symbol is ‘)’, it cannot match and can be discarded. 2. Add to stack if ‘(‘ is encountered.

3. Matches the first ‘(‘ in the stack, and leaves the stack with both markers set to 1.

4. Repeat 1 to 3 until the traversal is complete

5. The final statistical marker data is the maximum continuous length of 1. In this example, the maximum length for marking consecutive 1 is obviously 6, so the maximum valid parenthesis length is also 6.

Implementation code:

func longestValidParentheses(s string) int {
   var stack []int
   flag := make([]uint8.len(s))
   for i, c := range s {
      if len(stack) == 0 && c == ') '{
         / / step 1
         continue
      }
      if c == '(' {
         / / step 2
         stack = append(stack, i)
      } else {
         / / step 3
         flag[stack[len(stack)- 1]] = 1
         flag[i] = 1
         stack = stack[:len(stack)- 1]}}var m int
   / / step 5
   for i := 0; i < len(flag); i++ {
      var temp int
      for ; i < len(flag); i++  {
         if flag[i] == 1 {
            temp++
         } else {
            break}}if temp > m {
         m = temp
      }
   }
   return m
}
Copy the code

Submit result: (Leetcode broke down tonight, can not cut the picture: ⊙ :

Optimization idea:

Instead of using the tag array, you can start calculating the maximum length at the end of the traversal, effectively reducing the memory footprint and time complexity.