【Leetcode】32.最长有效括号

32.最长有效括号

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

  示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：

输入：s = ""
输出：0

方法一（栈）

  • 用栈来找出所有匹配的左右括号，并用一个列表来记录匹配括号的索引。

  • 于是这个列表中最长连续子序列的长度就是最长有效括号的长度。

    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
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        List<Integer> indexList = new LinkedList<>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(')
                stack.push(i);
            else{
                if(!stack.isEmpty()){
                    indexList.add(stack.pop());
                    indexList.add(i);
                }
            }
        }
        if(indexList.size() == 0)
            return 0;
        //寻找列表中最长连续子序列的长度
        Collections.sort(indexList);
        int max = 0;
        int index = 0;
        while(index < indexList.size() - 1){
            int count = 1;
            while(index < indexList.size() - 1 && indexList.get(index) == indexList.get(index + 1) - 1){
                count++;
                index++;
            }
            max = Math.max(count, max);
            index++;
        }
        return max;
    }

  • 时间复杂度：O(nlogn)

  • 空间复杂度：O(n) 栈和列表所需的额外空间

    方法二（动态规划）

    1.定义状态

    定义dp[i]为以位置i结尾的最长有效括号的长度

2.Base Case

  • 一个单括号不可能形成有效括号，因此dp[0] = 0

  • 如果1位置为右括号，0位置为左括号，那么dp[1] = 2

    3.状态转移

  • 如果i位置为左括号，那么没有以这个位置结尾的有效括号，dp[i] = 0

  • 如果i位置为右括号，分两种情况：

    • 如果i-1位置为左括号，那么i-1位置和i位置能组成一个长度为2的有效括号，再加上以i-2位置结尾的最长有效括号的长度，即为以i位置结尾的最长有小括号的长度。dp[i] = dp[i-2] + 2

    • 如果i-1位置为右括号，那么以它结尾可能会有一定长度的有效括号，我们先越过这些位置，来到这些匹配好的有效括号前面一个位置，如果这个位置是左括号，那么dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]

      例如："())(())"，对于位置5，其前面的位置4已经有长度为2的匹配好的有效括号"()"，并且它们前面的位置2为左括号，可以与位置5的右括号匹配，因此dp[i]肯定能在dp[i-1]的位置上加2。但如例子所示，以位置1结尾还有长度为2的有小括号，与之后的有小括号连上了，这时我们就需要把这部分有效括号的长度dp[i - dp[i - 1] - 2]也加上。

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
public int longestValidParentheses(String s) {
    if(s == null || s.length() < 2)
        return 0;
    int[] dp = new int[s.length()];
    //Base Case
    dp[0] = 0;
    dp[1] = s.charAt(1) == ')' && s.charAt(0) == '(' ? 2 : 0;
    int max = Math.max(dp[0], dp[1]);
    for(int i = 2; i < s.length(); i++){
        if(s.charAt(i) == '(')
            dp[i] = 0;
        else{
            if(s.charAt(i - 1) == '(')
                dp[i] = dp[i - 2] + 2;
            else{
                if(i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '('){
                    dp[i] = dp[i - 1] + 2;
                    dp[i] += i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0;
                }
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)