# Python DP solution

• ``````class Solution:
# @param {string} s
# @return {integer}
def longestValidParentheses(self, s):
if not s:
return 0
record = [0]*len(s)
left = []
for index, char in enumerate(s):
if char == "(":
left.append(index)
elif left:
leftIndex = left.pop()
if index>0 and index - leftIndex == record[index-1]+1:
record[index] = record[index-1] + 2
if leftIndex > 0:
record[index] += record[leftIndex-1]
return max(record)``````

• Can you post the recursive version of this code? It'll help people understand what's going on.

• ``````   def longestValidParentheses(self, s):
if len(s) == 0:
return 0
record = [0]*len(s)
left = []
for index, char in enumerate(s):
if char == "(":
left.append(index)
elif left:
leftIndex = left.pop()
if index>0 :
record[index] = index - leftIndex+1
if leftIndex > 0:
record[index] += record[leftIndex-1]
return max(record)``````

• It seems like recursive solution is very difficult to write for this problem. I will think about it.

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