An O(n^2) Python Solution. Not super fast, but really easy to understand


  • 0
    P

    The basic idea is that every long valid sequence is expanded from short one(s). There are two ways of expansion: either by concatenation (e.g., "()" + "()" => "()()") or by enclosure (e.g., "("+ "()" + ")" = "(())"). So you start from all shortest sequences, i.e., "()", and try to merge them or expand them. The algorithm stops when you can no longer do either of these two operations with your current set of sequences. The longest sequence should be there already. Therefore, this solution not only gives the length of the longest sequence but also the sequence itself.

    class Solution(object):
        def longestValidParentheses(self, s):
            stack = []
            for i in range(0, len(s) - 1):
                if s[i] == '(' and s[i + 1] == ')':
                    stack.append([i, i + 1])
    
            dirty = True
            while dirty:
                dirty = False
                nstack = []
                # merge
                for valid in stack:
                    if nstack:
                        last = nstack[-1]
                        if last[1] == valid[0] - 1:
                            last[1] = valid[1]
                            dirty = True
                            continue
                    nstack.append(valid)
                stack = nstack
                # expand
                for valid in stack:
                    if valid[0] > 0 and valid[1] < len(s) - 1:
                        if s[valid[0] - 1] == '(' and s[valid[1] + 1] == ')':
                            valid[0] -= 1
                            valid[1] += 1
                            dirty = True
            record = 0
            for start, end in stack:
                record = max(record, end - start + 1)
            return record

Log in to reply
 

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