32. Longest Valid Parentheses

题目

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

1
2
3
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

1
2
Input: s = ""
Output: 0

题目大意

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

解题思路

方法一：栈

思路

使用栈来跟踪括号的匹配情况。栈底始终保存当前最长有效括号子串的起始位置的前一个位置。

具体步骤：

  1. 初始化栈，将 -1 压入栈作为基准位置。
  2. 遍历字符串：
    • 遇到 '('，将当前索引压入栈。
    • 遇到 ')'，弹出栈顶元素：
      • 如果栈为空，将当前索引压入栈作为新的基准位置。
      • 如果栈不为空，计算当前索引与栈顶元素的差值，更新最长长度。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串长度。每个字符最多被压入和弹出栈一次。
  • 空间复杂度：O(n)，最坏情况下需要存储所有字符的索引。

方法二：动态规划

思路

使用动态规划数组 dp，其中 dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度。

状态转移：

  • 如果 s[i] == ')' 且 s[i-1] == '('，则 dp[i] = dp[i-2] + 2
  • 如果 s[i] == ')' 且 s[i-1] == ')' 且 s[i-dp[i-1]-1] == '('，则 dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2

复杂度分析

  • 时间复杂度：O(n)，仅需遍历一次字符串。
  • 空间复杂度：O(n)，需要额外的动态规划数组。

代码实现

方法一：栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        max_len = 0
        stack = [-1]
        
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        
        return max_len

方法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        max_len = 0
        dp = [0] * n
        
        for i in range(1, n):
            if s[i] == ')':
                if s[i-1] == '(':
                    dp[i] = dp[i-2] + 2 if i >= 2 else 2
                elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
                    dp[i] = dp[i-1] + (dp[i - dp[i-1] - 2] if i - dp[i-1] >= 2 else 0) + 2
                max_len = max(max_len, dp[i])
        
        return max_len

完整测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        max_len = 0
        stack = [-1]
        
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        
        return max_len

def test_longest_valid_parentheses():
    solution = Solution()
    
    s1 = "(()"
    print(f'Input: "{s1}"')
    print(f'Output: {solution.longestValidParentheses(s1)}')
    
    s2 = ")()())"
    print(f'\nInput: "{s2}"')
    print(f'Output: {solution.longestValidParentheses(s2)}')
    
    s3 = ""
    print(f'\nInput: "{s3}"')
    print(f'Output: {solution.longestValidParentheses(s3)}')
    
    s4 = "()(())"
    print(f'\nInput: "{s4}"')
    print(f'Output: {solution.longestValidParentheses(s4)}')

if __name__ == "__main__":
    test_longest_valid_parentheses()