Click here to see the full article post
For solution #4 should work with just one counter. Increment it on open, decrement on close, don't let it be negative, that's it.
Yes, you can do with one counter also. I thought two counters will make code more understandable.
In that case, you need another variable to store the length
It is correct. Output of ")(" is 0. The condition if(right>left) right=left=0 will handle this example.
Consider the input "(()" , left to right scan will output 0, but the answer is 2.
The dp approach maybe can simplify the IF condition of s[i-1] == '(' or ')'
just consider the s[i-1] == '(' is a kind of situation that dp[i-dp[i-1]-2] + dp[i-1] + 2
means that there is no Parenthese between '('(s[i-dp[i-1]-1]) and ')'(s[i])
class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ n = len(s) dp = *n ret = 0 for i in range(n): if s[i] == ')': if i - dp[i-1] > 0 and s[i-dp[i-1]-1] == '(': dp[i] = (dp[i-dp[i-1]-2] if i - dp[i-1] > 1 else 0) + dp[i-1]+2 ret = max(ret, dp[i]) return ret
@MitchellHe Try to submit again. It will get accepted.
For approach #4, the animation is wrong. In the left pass, when you reach index 1, the left/right counter should not be reset to 0.
@yangshun Thanks for pointing it out. I have corrected it. Thanks.
@MitchellHe Try to submit it 3-4 times, you will definitely get AC.
For approach #3, the code is right, but the last slide is wrong, 4 should be popped out first, so the answer is 7 - 3 = 4, maxlength is 4. Dummy head is a good idea.
So I had hard time understanding "stack" approach. Thank you for sharing.
For others who're also struggling to understand stack approach. Stack at any given point contains an index "after which valid substring could potentially start".
So begins with -1 (optimistically valid substring could start with 0 index)
Whenever "(" is encountered, assuming valid substring will begin after "(" (but excluding current "("'s position).
Whenever ")" is encountered, top of stack is pooped - this takes care of immediately previous "(" but optimistic assumption of immediately previous's previous "("'s index came true. So length is current index - top of stock. "(" always assume that valid string will be "after" "(", ")" pop top of stack (if not empty) and find length of valid string found. If ")" is encountered with empty stack. Assume valid string will begin after ")".
Cumulative pushing "(" (or ")" if stack is empty) takes care of extending substring with balanced parentheses.
Damn, the feeling you get when your intuition solves the problem is ineffable..Solved using stack approach..Thought I wouldn't be able to solve it without looking at the solution..But after 1 day of thinking and wondering, finally solved it. :)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.