78. LeetCode.32. 最长有效括号

• 标签： 动态规划
• 难度： 困难

---

• 题目描述

• 解法1： 错误

参考以前写的一道题: LeetCode 20. 有效的括号, 不难写出如下 代码。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        lefts = []
        result = 0
        i = 1
        while(i<len(s)):
            if s[i] == '(':
                lefts.append(i)
            if s[i] == '(' and not lefts:
                lefts.pop()
                result += 2
        return result

但是这段代码是错误的，因为忽略了有效子串必须连续. 一个错误示例：

• 解法2: 正确

新开一个长度等于 s 的数组 matched，如果在 ( 出栈时，也即发生匹配时， 在 matched 对应位置标记为匹配. 最后问题转化为求 0-1 数组中最长连续 1 子串的长度，用动态规划求解. 具体地， 遍历 matched 数组， 假设到了 i 位置， 用 L_i 记录 包含 matched[i] 的最长 1 子串长度, 若 matched[i] = 1, 则 L_i = L_(i-1) + 1, 若 matched[i] = 0, 则 L_i = 0； 用 ML_i 记录从 matched[0] 到 matched[i] 之内的最长连续 1 子串长度，ML_i = max(L_i, ML_(i-1)).

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        lefts = []
        matched = [0] * len(s)
    
        for i in range(0, len(s)):
            if s[i] == '(':
                lefts.append(i)
            if s[i] == ')' and lefts:
                j = lefts.pop()
                matched[i], matched[j] = 1, 1
        print(matched)
        L, ML = 0, 0
        for i in matched:
            if i:
                L +=1
            else:
                L = 0
            ML = max(ML, L)
        return ML
                

• 其他解法

暂略。