class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
# use 1D DP
# dp[i] records the longestValidParenthese EXACTLY ENDING at s[i]
dp = [0 for x in xrange(len(s))]
max_to_now = 0
for i in xrange(1,len(s)):
if s[i] == ')':
# case 1: ()()
if s[i1] == '(':
# add nearest parentheses pairs + 2
dp[i] = dp[i2] + 2
# case 2: (())
# idp[i1]1 is the index of last "(" not paired until this ")"
elif idp[i1]1 >= 0 and s[idp[i1]1] == '(':
if dp[i1] > 0: # content within current matching pair is valid
# add nearest parentheses pairs + 2 + parentheses before last "("
dp[i] = dp[i1] + 2 + dp[idp[i1]2]
else:
# otherwise is 0
dp[i] = 0
max_to_now = max(max_to_now, dp[i])
return max_to_now
Pure 1DDP without using stack (python) with detailed explanation


Thanks pennllio for the solution. Here is C++ version (8ms) of your solution:
class Solution { public: int longestValidParentheses(const string& s) { vector<int> v; for (int i = 0; i < s.length(); i++) { v.push_back(0); } int mx = 0; for (int i = 1; i < s.length(); i++) { if(s[i] == ')') { if(s[i1] == '(') { int val = 0; if(i  2 >= 0) { val = v[i2]; } v[i] = val + 2; if(mx < v[i]) { mx = v[i]; } } else { int j = i  v[i1]  1; if (j >= 0) { if(s[j] == '(') { int val = v[i  1] + 2; if(j  1 >= 0) { val = v[i  1] + 2 + v[j  1]; } v[i] = val; if(mx < v[i]) { mx = v[i]; } } } } } } return mx; } };

I think you don't need to add if dp[i1] >0 ...else...
I edit your code like this, and the system accepted, did I miss anything?class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ # use 1D DP # dp[i] records the longestValidParenthese EXACTLY ENDING at s[i] dp = [0 for x in xrange(len(s))] max_to_now = 0 for i in xrange(1,len(s)): if s[i] == ')': # case 1: ()() if s[i1] == '(': # add nearest parentheses pairs + 2 dp[i] = dp[i2] + 2 # case 2: (()) # idp[i1]1 is the index of last "(" not paired until this ")" elif idp[i1]1 >= 0 and s[idp[i1]1] == '(': dp[i] = dp[i1] + 2 + dp[idp[i1]2] max_to_now = max(max_to_now, dp[i]) return max_to_now


@flyerx
Why do you need another variablemax_to_now
? You could simply returnmax(dp)
Secondly, the condition check
if s[i1] == '(':
is unnecessary.def longestValidParentheses(self, s): s = ')' + s dp = [0] * len(s) for i in range(1, len(s)): if s[i] == ')' and s[i  dp[i  1]  1] == '(': dp[i] = dp[i  1] + 2 + dp[i  2  dp[i  1]] return max(dp)

@lee215 said in Pure 1DDP without using stack (python) with detailed explanation:
dp[i] = dp[i  1] + 2 + dp[i  2  dp[i  1]]
Could you explain your dp[i] = dp[i  1] + 2 + dp[i  2  dp[i  1]] function? Not sure how you came up with the last part

@zpng
for i in xrange(1,len(s))
So don't need bother a check.
Secondly, as I said in my previous reply, even theif s[i1] == '('
is unecessary.

python O(n) with stack, beat 93.66%
class Solution(object): def longestValidParentheses(self, s): if not s or len(s) < 2: return 0 stack = [] leftmost = 1 res = 0 for i in range(len(s)): if s[i] == '(': stack.append(i) else: # case ')' if not stack: # not valid parenthesis, update leftmost leftmost = i else: stack.pop() if not stack: # stack is empty, length is i  leftmost res = max(res, i  leftmost) else: # otherwise, length is i  last index of stack res = max(res, i  stack[1]) return res