This is the 23rd day of my participation in the More text Challenge. For more details, see more text Challenge

Longest valid parenthesis (question number 32)

The title

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

Example 1:

Enter: s ="()"Output:2Explanation: The longest valid parenthesis substring is"()"
Copy the code

Example 2:

Enter: s =") () ())"Output:4Explanation: The longest valid parenthesis substring is"() ()"
Copy the code

Example 3:

Enter: s =""Output:0
Copy the code

Tip:

  • 0 <= s.length <= 3 * 104
  • S [I] = '(' or ')

link

Leetcode-cn.com/problems/lo…

explain

This problem, this problem focuses on the idea.

The author himself did not think of any ideas, also know that there is a solution is DP, but here is not to come up with, there is no way, perhaps or solve the problem is not enough.

The website gives three kinds of answers, the author here to record the first two kinds of, the third kind is a bit too complicated, even if you understand the follow-up may not remember, also do not waste time.

The first is the stack operation, which is very similar to the other parenthesis problems, but you need to have a bottom element, or placeholder element, if you like.

The basic logic of the stack is the same as before, the last element of the stack is cancelled when it is encountered (pushed, encountered). The thing to notice here is that the pushed element is index.

There is a problem with using index, such as 🌰 :

"()"
Copy the code

If a simple push offsets the stack, the elements in the stack will look like this 👇 :

[0.1]
Copy the code

When you push in), the current index is 1, but the length is 2. How do you get the right length?

There are two ways of thinking about the first time:

  1. 1 minus 0 plus 1

    This kind of thinking is very simple, the difference of a position to fill, to solve the current situation is no problem.

  2. Insert a -1 in front of the stack and subtract the value of the element at the end of the stack from the current index

    Using this idea, the stack will look like this 👇 :

    [-1.0]
Copy the code

    In this case, the index is 1, so the length is 1 – -1, and you get 2.

Since there are two ways of thinking, which way is better? Don’t worry, let’s look at another case 👇 :

"() () ()"
Copy the code

First of all, if you use the first idea, this problem is GG, the simple reason is that the index is 2, the stack is empty.

As the insert continues, the result of the insert is 👇 :

[3.4]
Copy the code

At this point, you can still use 4 minus 3 plus 1 to get the right length, but what about the next two? Because it follows 👇 :

[5.6]
Copy the code

If you can only get a length of 2 by yourself, it is obviously wrong, so you have to use a new variable to temporarily store the length of the first, the case of a break, reset to 0, if you continue to open, you can continue to add, but there are no disadvantages except more trouble.

What about the second option? It’s relatively simple.

When index is 2, the negative 1 cances out and the stack is empty. When the stack is empty, the current index is pushed to the stack as a bottom value, so the stack looks like 👇 :

[-1]			/ / ""
[-1.0]			/ / "("
[-1]			/ / "()"
[2]			// "())"
Copy the code

The index of the stack is equal to 6, and the index of the stack is equal to 4.

Take a look at the overall process 👇 :

index The stack string The results of
[1] “” 0
0 [- 1, 0] “(“ 0
1 [1] “()” 1 minus minus 1 is 2
2 [2] “()” 0
3 [2, 3] “()” 0
4 [2] “())()” 4 minus 2 is 2
5 [2, 5] “() () (“ 0
6 [2] “() () ()” 6 minus 2 is 4

Therefore, the final maximum value is 4, which has one less variable to store the current progress compared with idea 1, and the idea is more clear.

The solution of DP is put in the answer, the content is too much may appear to see the front of the forgotten behind the case.

Your own answer

There is no

Better Approach (stack)

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

When the stack is empty, push the current index onto the stack.

A better approach (dynamic Programming)

DP says simple is simple, complicated is also a bit complicated.

Since you only need to look at the longest length, DP only needs a one-dimensional array, which is nothing to say.

The relationship between DP[I] and the previous one is important to consider 👇 :

  • The current element is (

    Since the current element cannot form a new closing parentheses, you only need to consider the longest valid parentheses of the previous element 👇 :

    dp[i] = dp[i - 1]
Copy the code

  • The current element is)

    • The previous element is (

      That’s going to form a new closed bracket, so all you have to do is get the value of I minus 2, plus 2.

      dp[i] = (dp[i - 2] | |0) + 2
Copy the code

    • The previous element is)

      So now we have two, so we need to find two.

      But if you think about it, you don’t need to, because the longest valid parenthesis of the previous one already has a value, which is dp[i-1].

      So what we need to think about now is whether there is a match for the current.

      Where to find them?

      We need to cross the maximum effective length of the previous element, which is dp[i-1]. We need to check whether s[i-dp [i-1] -1] is correct.

      • If it is, then it proves that it can form complete parentheses.

        And in this case you have to add (the maximum length in front, although it may not exist, if it does not exist, just give 0.

      • If it’s not, then don’t worry about it, because there’s no way to form valid parentheses, give up.

With this logic in mind, the code is simple 👇 :

var longestValidParentheses = function(s) {
  var len = s.length
      dp = new Array(len).fill(0)
  for (let i = 0; i < len; i++) {
    if (s[i] === ') ') {
      if (s[i - 1= = ='(') {
        dp[i] = (dp[i - 2] | |0) + 2
      } else if (s[i - dp[i - 1] - 1= = ='(') {
        dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] | |0)}}}return Math.max(... dp,0)};Copy the code

The realization is relatively simple, the key is whether the logic can be clear, can be clear on the complete need not worry, if you do not understand to see several times, the abstract logic here is really more around.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ