LeetCode32 最长有效括号

LeetCode第32题

问题描述

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

示例 1:

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

示例 2:

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

解题思路

本题的一种思路是使用栈，栈中元素保存[字符，最大长度]

1. 初始化栈stack和最大长度max_len

2. 遍历字符串

3. 如果当前字符是)，且栈顶元素stack[-1] = ['(', length]，那么：

   • 当前匹配长度 = length + 2

   • 弹出栈顶元素

   • stack[-1][1] += 当前匹配长度
   • max_len = max(stack[-1][1], max_len)

4. 否则，将['x', 0]压栈

5. 返回max_len即为最长有效括号

代码

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        stack, max_len = [['', 0]], 0
        
        for c in s:
            if ord(c) == ord(stack[-1][0]) + 1:
                count = stack[-1][1] + 2
                stack.pop()
                stack[-1][1] += count
                max_len = max(stack[-1][1], max_len)
            else:
                stack.append([c, 0])
        
        return max_len

另外一种解题思路是采用栈和动态规划：

1. 定义start变量记录合法括号串的起始位置
2. 遍历字符串
3. 如果遇到(，则将当前下标压入栈
4. 如果遇到)，则有两种情况：
   • 如果当前栈为空，则将下一个坐标位置记录到start
   • 如果当前栈不为空，则将栈顶元素取出
     • 若此时栈为空，最长值=max(最长值, 当前下标 - start + 1)
     • 否则最长值=max(最长值, 当前下标 - 栈顶元素值)

代码实现如下：

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack, res, start = [], 0, 0
        for i in range(len(s)):
            e = s[i]
            if e == '(':
                stack.append(i)
            else:
                if len(stack) == 0:
                    start = i + 1
                else:
                    stack.pop()
                    res = max(res, i - start + 1) if len(stack) == 0 else max(res, i - stack[-1])
        return res

此算法比上面的在空间复杂度上更优。