5-liner in Python, DP, 84ms


  • 0
    O

    Classic dp solution.

    class Solution(object):
        def longestValidParentheses(self, s):
            dp = [0] * len(s)
            for i in (i for i, c in enumerate(s) if i>0 and c == ')'):
                j = i-1 - dp[i-1]
                dp[i] = (2 + dp[i-1] + (dp[j-1] if j>=1 else 0)) if j>=0 and s[j]=='(' else 0
            return max(dp or [0])
    

    Which is equivalent to:

    class Solution(object):
        def longestValidParentheses(self, s):
            dp = [0] * len(s)
            maxL = 0
            for i in range(1, len(s)):
                if s[i] == ')':
                    j = i-1 - dp[i-1]
                    if j>=0 and s[j] == '(':
                        dp[i] = dp[i-1] + 2
                        if j-1>=0:
                            dp[i] += dp[j-1]
                        maxL = max(maxL, dp[i])
            return maxL
    

  • 0
    O

    @StefanPochmann Actually, I'm not very happy with my nested x if condition else y. How would you make it nicer?


Log in to reply
 

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