6-2

32. 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

A good python solution:

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [0]
        longest = 0
        
        for c in s:
            if c == "(":
                stack.append(0)
            else:
                if len(stack) > 1:
                    val = stack.pop()
                    stack[-1] += val + 2
                    longest = max(longest, stack[-1])
                else:
                    stack = [0]

        return longest

分析:

用到了栈的思想:后进先出。

遇左括号添0,遇右括号pop,从而保证当左右括号成对出现时对stack不会造成影响。

一开始栈并不设计成空的,而是保留有一个元素,是为了当全部的左右括号恰好匹配时,依然可以保存左右括号的数量,从而得到longest。

每次左右括号的值都保存在栈顶位置:stack[-1]。

如果有多余的右括号,则重置栈中的元素(相当于重新初始化为[0])。

上一篇:SPOJ Another Longest Increasing Subsequence Problem 三维最长链


下一篇:LeetCode 14. Longest Common Prefix