leetcode32-最长有效括号

原题

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

示例 1:

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

示例 2:

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

解法

思想

见代码部分

代码

动态规划解法:

dp[i]代表截至到某个元素的包含有效括号的子串的最长长度(必须包含该字符)。

那么若s.charAt(i) == '(',则dp[i]必为0。若s.charAt(i) == ')',分情况:
+ s.charAt(i-1) == '(',则字符串是...()的形式,此时的dp[i] == dp[i-2]+2
+ s.charAt(i-1) == ')',则字符串是...))的形式,此时要看与s.charAt(i-1)相匹配的左括号的前一个字符是否为(,若是,则dp[i] == dp[i-1]+2+dp[prev-1],若不是,则dp[i] == 0

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        int[] dp = new int[s.length()];
        for(int i = 1;i<dp.length;i++){
            if(s.charAt(i) != '('){ 
                if(s.charAt(i-1) == '('){
                    int prev = i>=2?dp[i-2]:0;
                    dp[i] = prev + 2;
                    if(dp[i]>max) max = dp[i];
                }else{
                    int prev = i-dp[i-1]-1;
                    if(prev>=0 && s.charAt(prev) == '('){
                        dp[i] = dp[i-1]+2 + (prev==0?0:dp[prev-1]);
                        if(dp[i]>max) max = dp[i];
                    }
                }
            }
        }
        return max;
    }
}

栈的解法需要一些精妙的设计,要保证栈底必须有一个元素(始终留下一个最左边没参与匹配的下标在栈内):

public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max = 0;

        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 {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode32-%e6%9c%80%e9%95%bf%e6%9c%89%e6%95%88%e6%8b%ac%e5%8f%b7/

发表回复

登录后才能评论