Leetcode算法Java全解答--32. 最长有效括号.md

Posted by lizhao on 07-09,2019

Leetcode算法Java全解答--32. 最长有效括号

[toc]

题目

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

示例 1:

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

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

想法

需用到辅助数组d[s.length()],表示从当前字符开始,到字符串结尾的最长有效括号子串长度(当前字符需为有效括号子串的第一个字符)

解题思路:从字符串结尾往前处理,求辅助数组d[]

当前字符下标为index,

若当前字符为左括号'(',判断index+1+d[index+1]位置的字符是否为右括号')',

若为右括号,则d[index] = d[index+1]+2,

并且判断index+1+d[index+1]+1位置的元素是否存在,若存在,

则d[index] += d[index+1+d[index+1]+1](解决上述两个有效括号子串直接相邻的情况)

结果

// TODO

总结

// TODO

代码

我的答案

class Solution {
    public int longestValidParentheses(String s) {
        if(null == s) return 0;
 
        int len = s.length(), max = 0;
        int[] d = new int[len];
 
        for(int index = len-2; index >= 0; index--){
            int symIndex = index+1+d[index+1];
            if('(' == s.charAt(index) && symIndex < len && ')' == s.charAt(symIndex)){
                d[index] = d[index+1]+2;
                if(symIndex+1 < len){
                    d[index] += d[symIndex+1];
                }
            }
 
            max = Math.max(max, d[index]);
        }
        return max;
    }
}

大佬们的答案

测试用例


其他

代码托管码云地址:https://gitee.com/lizhaoandroid/LeetCodeAll.git

查看其他内容可以点击专栏或者我的博客哈:https://blog.csdn.net/cmqwan

“大佬们的答案” 标签来自leetcode,侵权请联系我进行删改

如有疑问请联系,联系方式:QQ3060507060