python dp problem


  • 0
    Q
    class Solution(object):
        def longestValidParentheses(self, s):
            array=[0 for i in xrange(len(s))]#to store the length of parentheses substring which ends in i th ')'
            for i in range(len(s)):
                if s[i]==')':
                    j=i-1
                    while j>=0:
                        if s[j]=='(':#this is the matching one for s[i]
                            array[i]=j-i-1
                            break
                        if array[j]<0:#this ')' has a matching '(',so we go to that '(' 
                            j+=array[j]
                        else:
                            array[i]=0#ops,we meet a ')' with no pair
                            break
                    j=i
                    while j>=0:#here we manage to find the longest substring ending with this ')'
                        if array[j]<0:
                            j+=array[j]
                        else:
                            array[i]=j-i
                            break
                    if j==-1:
                        array[i]=j-i
            if len(array)==0:
                return 0
            return -min(array)
    

Log in to reply
 

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