Python DP O(n) without stack


  • 1
    X
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            if not s: return 0
            pleft = 0
            pmax = 0
            dp = [0]*len(s)
            for i in range(len(s)):
                if s[i] == '(':
                    dp[i] = 0
                    pleft+=1
                else:
                    if pleft < 1:dp[i] = 0
                    else:
                        pleft-=1
                        dp[i] = 2 + dp[i-1] + dp[i-2-dp[i-1]]
                        pmax = max(pmax,dp[i])
            return pmax
    

  • 0
    P

    Thanks for sharing your solution @xuhongnever. Would you explain your logic behind the line dp[i] = 2 + dp[i-1] + dp[i-2-dp[i-1]] ?


  • 0
    X

    @pg2286 Thank you for viewing my answer !
    The current Parentheses string can be divided into three parts **part 1**(**part 2**), the two parentheses is part 3
    So the current string length should Part 3 : 2 + part 2: dp[i-1] + part 1 : dp[i-2-dp[i-1]].


Log in to reply
 

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