O(n) time python with one stack


  • 0
    Z
    class Solution(object):
        def longestValidParentheses(self, s):
            def add_range(pair, ranges):
                if not ranges:
                    ranges.append(pair)
                    return
                prev_pair = ranges.pop()
                if prev_pair[1] < pair[0] - 1:
                    ranges.append(prev_pair)
                    ranges.append(pair)
                    return
                if prev_pair[0] > pair[0] and ranges:
                    prev_pair = ranges.pop()
                if prev_pair[1] == pair[0] - 1:
                    ranges.append((prev_pair[0], pair[1]))
                    return
                ranges.append(prev_pair)
                ranges.append(pair)
                
            stack = []
            ranges = []
            for i, p in enumerate(s):
                if p == '(':
                    stack.append(i)
                elif stack:
                    start = stack.pop()
                    add_range((start, i), ranges)
            if not ranges:
                return 0
            max_range = max(ranges, key=lambda p:p[1]-p[0])
            return max_range[1] - max_range[0] + 1

Log in to reply
 

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