美文网首页
32. Longest Valid Parentheses

32. Longest Valid Parentheses

作者: 阿团相信梦想都能实现 | 来源:发表于2016-12-09 09:35 被阅读0次
    using dynamic programming 
    ***
    s=’(()(())’
    dp[7]=以s[6]为结尾的longest valid parentheses substring 长度
    j=7-2-dp[6]=5-2=3
    j>0 and s[3]=’(‘
    d[7]=d[6]+2+d[3]=2+2+2=6
    
    s=’(())())’
    j=7-2-dp[6]=5-2=3
    s[3]!=’(‘
    d[7]=0
    ****
    
    
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            if len(s)==0:
                return 0
            max_len=0
            dp=[0]*(len(s)+1)
            for i in range(1,len(s)+1):
                if s[i-1]=='(':
                    dp[i]=0
                else:
                    j=i-2-dp[i-1]
                    if j>=0 and s[j]=='(':
                        dp[i]=dp[i-1]+2+dp[j]
                        max_len=max(max_len,dp[i])
                    else:
                        dp[i]=0
                    
            return max_len
    
    using stack 
    
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            stack=[]
            start=0
            max_length=0
        
            for i in range(len(s)):
                if s[i]=='(':
                    stack.append(i)
                    
                elif s[i]==')':
                    if len(stack)==0:
                        start=i+1
                    else:
                        stack.pop()
                        if len(stack)==0:
                            max_length=max(max_length,i-start+1)
                            
                        else: 
                            max_length=max(max_length,i-stack[-1])
    
    
            return max_length
                        
    

    相关文章

      网友评论

          本文标题:32. Longest Valid Parentheses

          本文链接:https://www.haomeiwen.com/subject/pbdemttx.html