Python DP with Stack O(n) 76ms


  • 0

    iterate through the string while adding to stack if char is '('. If the current char is ')', pop the stack to see where the current bracket started. Key is to memoize where each bracket group starts and ends then looping through to see if there was a bracket group that ended right before the start of the current bracket group. Optimized memory usage a bit by removing intra bracket groups from storage.

        def longestValidParentheses(self, s):
            stack, memo, mx = [], {}, 0
            for i in range(len(s)):
                if s[i] == '(': 
                    stack.append(i)
                else:
                    if not stack: continue
                    st = stack.pop()
                    while st-1 in memo:
                        temp = st-1
                        st = memo[temp]; del memo[temp]
                    mx = max(mx, i-st+1)
                    memo[i] = st
            return mx
    

Log in to reply
 

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