Python DP solution


  • 1
    C
    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)

  • 0
    H

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


  • 0
    Y
       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)

  • 0
    C

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


Log in to reply
 

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