32. 最长有效括号

发表评论
375 views

 ›
32. 最长有效括号

官方链接

https://leetcode-cn.com/problems/longest-valid-parentheses

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

示例 1:

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

示例 2:

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

解法一

暴力解法(超出时间限制)

class Solution {
    public Boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') stack.push(')');
            else {
                if (stack.isEmpty()) return false;
                if(stack.peek() == c) stack.pop();
                else return false;
            }
        }
        return stack.isEmpty();
    }
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i+1; j < s.length(); j++) {
              if(isValid(s.substring(i, j+1))) {
                  maxLen = Math.max(maxLen, j-i+1);
              }
            }
        }
        return maxLen;
    }
}

解法二

动态规划

class Solution {
    public int longestValidParentheses(String s) {
        int maxlen = 0;
        int[] dp = new int[s.length()];

        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) != ')') continue;
            if(s.charAt(i-1) == '(') {
                dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
            } else if (i - dp[i-1] > 0 && s.charAt(i-dp[i-1]-1) == '(') {
                dp[i] = dp[i-1] + ((i - dp[i-1]) >= 2 ? dp[i - dp[i-1]-2] : 0) + 2;
            }
            maxlen = Math.max(maxlen, dp[i]);
        }
        return maxlen;
    }
}

解法三

栈

class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if(stack.empty()) stack.push(i);
                else maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
        return maxLen;
    }
}