# Pure 1D-DP without using stack (python) with detailed explanation

• ``````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[i-1] == '(':
# add nearest parentheses pairs + 2
dp[i] = dp[i-2] + 2
# case 2: (())
# i-dp[i-1]-1 is the index of last "(" not paired until this ")"
elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
if dp[i-1] > 0: # content within current matching pair is valid
# add nearest parentheses pairs + 2 + parentheses before last "("
dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
else:
# otherwise is 0
dp[i] = 0
max_to_now = max(max_to_now, dp[i])
return max_to_now``````

• 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[i-1] == '(') {
int val = 0;
if(i - 2 >= 0) {
val = v[i-2];
}
v[i] = val + 2;
if(mx < v[i]) {
mx = v[i];
}
} else {
int j = i - v[i-1] - 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;
}
};``````

• This post is deleted!

• @pennlio

I think you don't need to add if dp[i-1] >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[i-1] == '(':
# add nearest parentheses pairs + 2
dp[i] = dp[i-2] + 2
# case 2: (())
# i-dp[i-1]-1 is the index of last "(" not paired until this ")"
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]
max_to_now = max(max_to_now, dp[i])
return max_to_now

``````

• @flyerx right, somehow that's hidden in dp = [0 for x in xrange(len(s))]

• @flyerx
Why do you need another variable `max_to_now`? You could simply return `max(dp)`

Secondly, the condition check `if s[i-1] == '(':` 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)``````

• 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

• thank you for your explantion

• ``````                if s[i - 1] == '(':
dp[i] = (0 if i < 2 else dp[i - 2]) + 2

``````

I think you should add a check of index out of range

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

• You are not using Stack and using an array.
In python, we can use array/list as a stack.
And this stack will consume less memory than the array being used by DP solutions.

• ### 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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.